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

1. G₁U G₂ жәнеG₁хG₂ графтары үшін:

Цикломатикалық санды;

Хроматикалық санды;

Диаметр, радиус, центрді табыңыз.

Бұл графтардың эйлер графы болуын тексеріңіз. Барлық қаңқалы ағаштарды белгілеңіз.

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

Пусть V — конечное множество и

І_V ={(v, v): v V}.

Важное свойство отношения ~ сформулировано в следующем утверждении.

Утверждение. Отношение ~ является отношением эквивалентности на V²-.

Доказательство оставляем в качестве упражнения.

Множество эквивалентных классов, определенное таким образом, обозначим через V²-/~. Каждый класс эквивалентности содержит ровно два элемента, так как если (v₁, v₂) V²-, то [(v₁, v₂)]={(v₁, v₂), (v₂, v₁)}. Здесь [(v₁, v₂)]— класс эквивалентности, содержащий (v₁, v₂).

Дадим строгое определение графа.

Определение. Графом G называется пара G = (V, E), где V —непустое конечное множество вершин, а Е — подмножество V²-/~

Другими словами, можно сказать, что граф G есть пара G = (V, Е), где V — непустое конечное множество вершин, а Е — множество неупорядоченных пар различных вершин.

Множество Е называют множеством ребер графа, |V| обозначает число вершин G, |Е| —число ребер G.

Следующий результат выражает связь между графами и классами отношений на конечных множествах.

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

а) Граф G = (V, E) определяет нерефлексивное симметричное отношение на V.

б) Нерефлексивное симметричное отношение на конечном множестве V определяет граф.Доказательство.

а) Пусть G=(V, E) — граф. Определим отношение R(E) на V следующим образом: v₁R(E)v₂ тогда и только тогда, когда [v₁, v₂] E, Отношение R(E) нерефлексивно, так как vR(E)v тогда и только тогда,

—

для v₁R(E)v₂ тогда и только тогда, когда [v₁, v₂] E, однако