Главная » Файлы » Методички » Экстремальные задачи [ Добавить материал ]

Теория графов - самые основные понятия

Граф (от греческого "пишу") - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

Ребро - неупорядоченная пара вершин.
Дуга - упорядоченная пара вершин.

То-есть дуга имеет определённое направление, а ребро нет.

Граф, содержащий только ребра, называется неориентированным (или неорграфом);
Граф, содержащий только дуги - ориентированным (или орграфом).

Кратные дуги и рёбра - когда две вершины соединены несколькими рёбрами. либо несколькими однонаправленными дугами.

Мультиграф - граф, имеющий кратные дуги или рёбра.

Дуга (или ребро) может начинаться и заканчиваться в одной и той же вершине, в этом случае соответствующая дуга (или ребро) называется петлей.

Псевдограф — граф, содержащий петли.

Вершины, соединенные ребром или дугой, называются смежными.
Ребра, имеющие общую вершину, тоже называются смежными.

Инцидентность
— понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1  и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут.

Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки (когда вершины представляются точками, а дуги и рёбра - стрелками и линиями соответственно) таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это неверно.

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер (дуг).

Полный граф - граф. в котором каждая вершина соединена с каждой.
Полный граф — простой граф, в котором каждая пара различных вершин смежна.

Полустепень захода (исхода) вершины – количество дуг, заходящих (выходящих) в (из) вершину (ы).

Степень (валентность) вершины - это количество вершин, соединённых с данной вершиной, либо - количество рёбер графа, инцидентных данной  вершине.

Голая вершина графа - изолированная вершина без петель.

Изолированная вершина
— вершина, не соединённая с другими вершинами ни дугами, ни рёбрами. однако такая вершина может иметь петли. Так же можно сказать, что это вершина без инцидентных ей дуг или ребер. А в случае графа без петель это вершина степени 0 (кстати говоря такую вершину уже можно назвать голой).

Вход и выход графа - вершины, имеющие соответствующее смысловое значение в рамках конкретной задачи.

Путь (маршрут) — последовательность рёбер  (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему.

Цепь в графе — маршрут, все рёбра которого различны.

Простой граф — граф, в котором нет кратных рёбер и петель.

Простой путь — путь, все рёбра которого попарно различны. Другими словами, простой путь не проходит дважды через одно ребро.

Ориентированный граф G(V, X) называется односторонне связным, если для любой пары вершин vi, vj существует путь  либо из vi в vj, либо из vj в vi.

Ориентированный граф G(V, X) называется сильно связным, если для любой пары вершин vi, vj существует путь и из vi в vj, и из vj в vi.



Эйлеровым путём (цепью) в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз.

Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).

Гамильтонов путь (или гамильтонова цепь) — путь, содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф.

Контур — замкнутый путь в орграфе.

Критический путь графа — путь максимальной длины в ориентированном ациклическом графе.

Добавил: COBA (20.06.2010) | Категория: Экстремальные задачи
Просмотров: 5038 | Загрузок: 0 | Рейтинг: 0.0/0 |
Комментарии (0)

Имя *:
Email *:
Код *: