Реферат: Теория графов

Обозначение: O ' – граф с вершинами, не имеющий ребер (рис. 2.2).

(РИСУНОК 2.2)

Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным .

Обозначение: U ' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n –угольник, в котором проведены все диагонали (рис. 2.3).

(РИСУНОК 2.3)

Определение 2.05. Степенью вершины называется число ребер, которым принадлежит вершина.

Обозначение: p (A ) – степень вершины A . Например, на рисунке 2.1: p (A )=2, p (B )=2, p (C )=2, p (D )=1, p (E )=1.

Определение 2.06. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k .

На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.

(РИСУНОК 2.4 и 2.5)

Определение 2.07. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

На рисунке 2.6 изображен исходный граф G , состоящий из четырех вершин и трех отрезков, а на рисунке 2.7 – дополнение данного графа – граф G ' .

(РИСУНОК 2.6 и 2.7)

Мы видим, что на рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах (этот вопрос будет рассмотрен подробно далее, в параграфе 5).

Определение 2.08. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским .

Например, на рисунке 2.8 показан плоский граф, изоморфный (равный) графу на рисунке 2.5. Однако, заметим, что не каждый граф является плоским, хотя обратное утверждение верно, т. е. любой плоский граф можно представить в обычном виде.

(РИСУНОК 2.8)

Определение 2.09. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью .

Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт (подробнее об этом – в §4).

Определение 2.10. Путем от A доX называется последовательность ребер, ведущая от A к X , такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Например, на рисунке 2.9 дан граф G ' , на которомпроложен путь от C доH :(C , F ); (F , B ); (B , A ); (A , H )или (C , D ); (D , E ); (E , A ); (A , H ).

(РИСУНОК 2.9)

Определение 2.11. Циклом называется путь, в котором совпадают начальная и конечная точка.

Вот пример цикла, проложенного на графе G (рис. 2.9): (A , B ); (B , F ); (F , C ); (C , D ); (D , E ); (E , A ).

Определение 2.12. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

Определение 2.13. Длиной пути , проложенного на цикле, называется число ребер этого пути.

Пример: на графе G (рис. 2.9) проложен простой цикл (A , B ); (B , F ); (F , C ); (C , D ); (D , E ); (E , A ) длина пути этого цикла равна 6.

Определение 2.14. Две вершины A иB в графе называются связными (несвязными ), если в нем существует (не существует) путь, ведущий из A в B .

Определение 2.15. Граф называется связным , если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным .