Сабақ Тақырыбы: Цикломатикалық сан. Хроматикалық сан. Графтардағы жолдарды және ең қысқа жолдарды анықтау. Тапсырмалар

жүктеу 220,97 Kb.

бет	2/5
Дата	19.01.2022
өлшемі	220,97 Kb.
	#33399
түрі	Сабақ

1 2 3 4 5

№7 практикалық сабақ ммм

[v₁, v₂] = { v₁, v₂), (v₂, v₁)} = [v₂, v₁]. Следовательно, v₁R{E)v₂ тогда и только тогда, когда v₂R(E)v₁.

б) Если R — нерефлексивное симметричное отношение на V, то

R V² .

—

Нерефлексивность R означает, что (v, v) R для любого v V, поэтому

R V² .

—

Симметричность R означает, что (v₁, v₂) R тогда и только тогда, когда (v₂, v₁) R. Определим Е формулой E = R/~, тогда G = (V, E) есть искомый граф.

Графы могут быть представлены матрицами с булевыми элементами. Многие из свойств графов могут быть определены из их матричных представлений путем алгебраических преобразований. Это станет понятньш из последующего изложения.

Определение. Матрица смежности А M(п, В) графа G = (V, E), где

|V|=n, определяется следующим образом:

Говорят, что вершины v_i и v_j являются смежными, если A_ij= 1. Ясно, что А_ii =0 (i=1,..., п) и А=А^Т. Таким образом, А симметрична, и

А = А(R(Е)).

Изображение графа G = (V, E) получается путем расположения различных точек на R² для каждой v V, причем, если [v, w] E, мы проводим линию, соединяющую вершины v и w.

Пример 1. Пусть

Этот граф изображен на рис. 1.

Рис. 1.

Этот граф изображен на рис. 2.

Рис. 2.
Графы являются скорее «топологическими», чем «геометрическими» объектами, т. е. они выражают больше отношения между вершинами, чем расположение вершин и ребер в пространстве. Таким образом, граф может быть изображен бесконечным количеством разных, но

«эквивалентных» способов. Однако изображения графов могут вводить в заблуждение. Например, из пересечения двух ребер на рисунке не следует, что точка пересечения является вершиной (см. первую диаграмму на рис. 2). Ясно, что нижней (верхней) треугольной части матрицы смежности достаточно, чтобы определить граф.

Дадим следующие определения.

Определение. Говорят, что граф H = (V₁, Е₁) является подграфом графа G = (V, Е), если V₁ V и Е₁ E. Если V₁ = V, то говорят, что H является остовным подграфом G. Если V₁ — непустое подмножество вершин графа (V, Е), то подграф (V₁, Е₁), порожденный V₁, определяют как

Определение.

а) Пусть G₁=( V₁, E₁) и G₂ = (V₂, E₂) — графы. Будем говорить, что G₁ и

G₂ эквивалентны, если существует биекцпя f: V₁ → V₂ такая, что

б) Пусть G=(V, E) — произвольный граф. Определим отображение

следующим образом: величина δ(v) равна числу ребер, содержащих вершину x V. Назовем δ(v) степенью вершины v.

Следующее утверждение выражает два простых, но важных факта о свойствах графов.

Утверждение.

б) В любом графе число вершин нечетной степени четно. Доказательство. Каждое ребро дважды входит в сумму, откуда и следует утверждение.

в) Пусть V_е V —множество вершин четной степени, a V₀ V — множество вершин нечетной степени. Заметим, что

следовательно,

(Ясно, что где k — некоторое целое.) Таким образом,

т. е. четно, однако каждое δ (v) в левой части нечетно, поэтому |V| четно.

Во многих приложениях теории графов о топологии графа имеется дополнительная информация, относящаяся к V, или к Е, или к обоим множествам одновременно. Чтобы конкретизировать вышесказанное, определим понятие помеченного графа и дадим несколько примеров. Определение.

Пусть S_V и S_E — множества меток. Пометкой или распределением меток графа G = (V, E) называется пара функций

жүктеу 220,97 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5