Опр.: Пусть X некоторое множество произвольных элементов и V множество всех неупорядоченных пар элементов из X.Пара множеств G=(X,E), где E содержться(подкова с подчеркиванием) в V наз. графом(неориентированным графом).
Опр.: Если две вершины x и y образуют ребро в графе G будем говорить что вершины X и y смежны.
Опр.: Ребра e1 И e2 являются смежными если содержат общую вершину.
Опр.: Инцидентность—понятие, используемое только в отношении ребра и вершины: если x,y — вершины, а e = (x,y) — соединяющее их ребро, тогда вершина x и ребро e инцидентны, вершина y и ребро e тоже инцидентны.
Опр.: Степень вершины — количество рёбер графа G, инцидентных вершине x, обозн. d(x), deg(x).
Опр.: Граф не соедржащий ребер наз. пустым графом и обозн. О с индексом n(кол-во вершин).
Опр.: Граф в котором любые две вершины смежны наз. полным и обозн. K с индексом n(кол-во вершин).
Замечание: О с индексом 1 тоже что и K с индексом 1, одинаково.
Опр.: Граф G=(X,E) наз. двудольным если множество его вершин X можно разбить на два непересекающихся множества(доли), X=X1обединениеX2, X1пересечениеX2=пусто и любое ребро графа G имеет один конец в доле X1, а другой в X2.
Опр.: Двудольный граф наз. полным если любая вершина доли X1 смежна с вершинами доли X2, если |X1|=p, |X2|=q, то полный двудольный граф обозн. K с индексами p,q.
Лемма(о рукопожатях): Для любого графа G=(X,E) сумма степеней всех вершин графа равна удвоенному кол-ву ребер этого графа.
Утверждение: В любом неориентированном графе число вершин нечетной степени четно.
Опр.: Граф H=(Y,V) наз. подграфом графа G, если Yподмножество(Подкова с подчеркиванием, "из")X, V(Подкова с подчеркиванием)E.
Опр.: Граф H=(Y,V) наз. остовным подграфом графа G, если Y=X, Vподмножество(Подкова с подчеркиванием, "из")E.
Опр.: Граф H=(Y,V) наз. подграфом графа G порожденным множеством Y если Yподмножество(Подкова с подчеркиванием, "из")X, а V содержит все ребра графа G оба конца которых принадлежат множеству V.
Опр.: Граф G(черта свеху) с множеством вершин X в котором 2 вершины с межны тогда и только тогда, когда они не смежны в графе G наз. графом дополнением графа G.
Опр.: Графы G и H наз. изоморфными если сущ. отображение фи:X"стрелка"Y (биективное) таоке что для любых 2-х вершин u,v"принадлежащих"X их отображение фи(u) и фи(v) смежны в графе H тогда и только тогда, когда вершины u,v смежны в графе G.
1 Основные понятия теории графов : Граф (неориентированный), смежность (вершин, ребер), инцидентность, степень вершины, подграфы ,типы подграфов: пустой ,полный и двудольный.
граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
• V это множество вершин или узлов,
• E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.
Степень вершины — количество рёбер графа G, инцидентных вершине x. Обозначается d(x). Минимальная степень вершины графа G обозначается ?(G). а максимальная — ?(G).
Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству.
Пустой граф (вполне несвязный граф, нуль-граф) — регулярный граф степени 0, то есть граф, не содержащий рёбер.
Полным графом называется граф, в котором для каждой пары вершин v1,v2, существует ребро, инцидентное v1 и инцидентное v2 (каждая вершина соединена ребром с любой другой вершиной)
Двудольный граф (или биграф, или чётный граф) — это граф G(V,E), такой что множество вершин V разбито на два непересекающихся подмножества V1 и V2, причём всякое ребро E инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). То есть, правильная раскраска графа двумя цветами. Множества V1 и V2 называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из V1 и V2 являются смежными. Если , , то полный двудольный граф обозначается Ka,b.