Graphs Flashcards
Граф
Графом называется упорядоченная пара (V, E), где V — непустое множество вершин, E — множество рёбер (множество парных связей.
(n, m)-графом называется граф, содержащий n вершин и m рёбер.
Порядок графа — число его вершин.
Смежные вершины и рёбра графа
Две вершины u и v называются смежными ( u ~ v ), если uv является ребром.
Рёбра e1, e2 называются смежными, если они имеют общий конец, то есть их пересечение не пусто.
Инцидентные вершина и ребро
Вершина v и ребро e называются инцидентными, если вершина принадлежит ребру
Окружение вершины v
Множество вершин х из V, таких, что vx — ребро.
Окружение — множество вершин, смежных с заданной.
Степень вершины
Степенью вершины v называется мощность множества ее окружения.
deg(v) = | N(v) |
Изолированная, концевая, доминирующая вершина
Вершина называется изолированной, если её степень равна 0. Вершина называется концевой, если её степень равна 1. Вершина называется доминирующей, если она смежна си всеми остальными вершинами.
Лемма о рукопожатиях и её следствие
Лемма: Сумма степеней вершин произвольного графа является четным числом и равна удвоенному числу рёбер графа.
Следствие: в произвольном графе число вершин с нечётными степенями является чётным числом
Полный, пустой, помеченный граф
Граф называется полным, если любые две его вершины смежны.
Граф называется пустым, если все вершины изолированы.
Граф называется помеченным, если его вершинам присвоены некоторые метки.
Равные графы
Если граф G = H, то E(G) = E(H) и они помечены одинаковыми метками.
Изоморфные графы
Графы G и H называются изоморфными, если существует биекция Y : V(G) — V(H) и для любых смежных вершин u,v эта биекция сохраняет их смежность
Связный граф
Граф связный, если любые две его вершины соединены маршрутом
Связная компонента графа
Связной компонентой графа называется всякий максимальный относительно включения связный подграф
Маршрут в графе
Чередующаяся последовательность вершин и рёбер (v1, e1, v2, e2…), в которой любые два соседних элемента инцидентны.
Цикл
Замкнутая цепь
Свойства маршрутов
1) Если вершины u != v, то любой (u,v) маршрут содержит в себе простую (u,v) цепь
2) Всякий цикл содержит с себе простой цикл
3) Объединение двух несовпадающих простых цепей содержит простой цикл
Подграф
Граф H называется подграфом G, если V(H) содержится в V(G) и E(H) содержится в E(G)
Разновидности маршрутов
1) Цепь (маршрут, который не содержит повторяющихся рёбер)
2) Простая цепь (маршрут, который не содержит повторяющихся вершин, кроме крайних)
3) Замкнутый маршрут (начало и конец совпадают)
Теорема 2 о числе компонент
Пусть | G | = n, k(G) = k — число компонент, тогда выполняется неравенство:
n - k не превосходит (n-k+1)(n-k)/2
Двудольный граф
Граф называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V1 и V2, причём всякое ребро соединяет вершину из V1 с вершиной из V2
Расстояние между вершинами графа
Пусть G — связный граф, тогда расстоянием между его вершинами u и v называется величина d(u,v), равная минимальной длине из (u,v)-маршрутов
Теорема 3 (о волновом алгоритме)
Пусть G — связный граф, обработанный волновым алгоритмом с начальной вершиной uo. Тогда метка l(u) = d(uo, v) для любого v из V
Полный двудольный граф
Граф G(A,B) называется полным двудольным, если каждая вершина из A смежна с каждой вершиной из B.
Самодополнительный граф
Граф называется самодополнительным, если он изоморфен своему дополнению
Теорема Кёненга
Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины
Следствие (критерий двудольности)
Пусть связной граф обработан волновым алгоритмом, тогда граф является двудольным тогда и только тогда, когда никакие два вершины с одинаковыми метками не являются смежными
Дерево, лес
Деревом называется связный граф, не содержащий циклов. Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья
Остовное дерево
Остовным деревом связного графа называется ациклический связный подграф, в который входят все вершины данного графа
Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все n вершин исходного графа и содержит n-1 ребро.
Сколько рёбер нужно удалить из графа для получения остова
m - n + k, где n = | G |, m = | E(G) |, k = k(G)
Теорема Кирхгофа
Число остовных деревьев в связном помеченном графе порядка n >= 2 равно алгебраическому дополнению произвольного элемента матрицы Кирхгофа
Абстрактные графы
Графы, которые различаются в точности до изоморфизма
