4. Теоремы графических разбиений.
5. Пути и связность в неориентированном графе.
Неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это непустое множество вершин или узлов,
E это множество неупорядоченных пар вершин, называемых рёбрами.
V и Е обычно считаются конечными множествами.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа. Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}. Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды). Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута. Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
Здесь приведены некоторые критериальные (эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:
У него одна компонента связности
Существует путь из любой вершины в любую другую вершину
Существует путь из заданной вершины в любую другую вершину
Содержит связный подграф, включающий все вершины исходного графа
Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)
При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп
6. Графы и бинарные отношения
Бинарным отношением на множестве A называется любое подмножество R множества A2, состоящего из всевозможных упорядоченных пар элементов множества A. Каждому такому отношению можно поставить в соответствие граф отношения G = (A, R). Сравнивая с тем, что говорилось выше об определениях различных типов графов, видим, что понятие бинарного отношения эквивалентно понятию ориентированного графа с петлями. Другие типы графов без кратных ребер – это частные виды бинарных отношений. Отношение R называется рефлексивным, если для любого x ∈ A пара (x, x) принадлежит R, и антирефлексивным, если ни одна такая пара не принадлежит R. Отношение называется симметричным, если из (x, y) ∈ R следует, что (y, x) ∈ R. В графе антирефлексивного и симметричного отношения нет петель и для каждой пары вершин либо нет ни одного, либо есть два ребра, соединяющих этивершины. Если в таком графе каждую пару ориентированных ребер, соединяющих одни и те же две вершины, заменить одним неориентированным ребром, то получится обыкновенный граф.