Самостоятельная работа-4 Студент: 2 курс Группа: ди-13-20

Неориентированным графом (англ. undirected graph) называется пара , где — множество вершин, а — множество рёбер. Определение: Ребром в неориентированном графе называют неупорядоч енную пару вершин .
Неориентированный граф G = (V, Е) состоит из конечного множества вершин V и множества ребер Е. В отличие от ориентированного графа здесь каждое ребро (v, w) соответствует неупорядоченной паре вершин¹: если (v, w) - неориентированное ребро, то (v, w) = (w, v). Далее неориентированный граф будем называть просто графом.
Графы широко используются в различных областях науки и техники для моделирования симметричных отношений между объектами. Объекты соответствуют вершинам графа, а ребра - отношениям между объектами [1]. В этой главе будут описаны различные структуры данных, которые применимы для представления графов. Также будут рассмотрены алгоритмы решения трех типовых задач, возникающих при работе с графами: построения минимальных остовных деревьев, определения двусвязных компонент и нахождения максимального паросочетания графа.
Основные определения
Многое из терминологии ориентированных графов применимо к неориентированным графам. Например, вершины v и w называются смежными, если существует ребро (v, w). Будем также говорить, что ребро (v, w) инцидентно вершинам v и ж
Путем называется такая последовательность вершин Vi, v₂, v_w, что для всех /, 1 < / < п существуют ребра (v„ и, v, + i). Путь называется простым, если все вершины пути различны, за исключением, возможно, вершин V/ и v„. Длина пути равна количеству ребер, составляющих путь, т. е. длина равна п - 1 для пути из п вершин. Если для вершин v, и v„ существует путь vi, v₂, ..., v_m то эти вершины называются связанными. Граф называется связным, если в нем любая пара вершин связанная.
Пусть есть граф G = (V, Е) с множеством вершин V и множеством ребер Е. Граф G = (Г, Е) называется подграфом графа G, если:
1) множество V является подмножеством множества V;
2) множество Е состоит из ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V. ^ока не будет сказано другое, будем считать, что ребро всегда соответствует паре различных вершин.
Если множество Е состоит из всех ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V ₉ то в этом случае граф G называется индуцированным подграфом графа G.