Теория графов

| Категория реферата: Рефераты по математике
| Теги реферата: сочинение сказка, отчет по производственной практике
| Добавил(а) на сайт: Wegolev.

Обозначение: 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. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

(РИСУНОК 2.10 и 2.11)

На рисунке 2.10 изображен связный граф; на рисунке 2.11 – несвязный
(т. к. существует минимум одна пара несвязных вершин – A и D).