№ 7-8 практикалық сабақ
Тақырыбы: Цикломатикалық сан. Хроматикалық сан. Графтардағы жолдарды және ең қысқа жолдарды анықтау.
Тапсырмалар:
1. G1U G2 жәнеG1хG2 графтары үшін:
Цикломатикалық санды;
Хроматикалық санды;
Диаметр, радиус, центрді табыңыз.
Бұл графтардың эйлер графы болуын тексеріңіз. Барлық қаңқалы ағаштарды белгілеңіз.
Тапсырмалар нұсқалары:
Число ребер в маршруте называется его длиной. Длина маршрута на рис. 6 равна 4. Началом и концом маршрута называются вершины, инцидентные его первому и последнему ребру, но не инцидентные второму и предпоследнему (обратите внимание на формальность определения!). Если начало совпадает с концом, маршрут называется циклическим.
Многие отношения на конечных множествах могут быть изображены в виде рисунков, с которыми можно работать при помощи соответствующих матриц. Перед тем как определить конструкции этих рисунков, необходимо быть уверенными в том, что это не повлечет за собой никаких двусмысленностей. Введем необходимые понятия.
Пусть V — конечное множество и
ІV ={(v, v): v V}.
Положим
V2-= V2\ ІV ={(v1, v2): v1≠ v2}
Важное свойство отношения ~ сформулировано в следующем утверждении.
Утверждение. Отношение ~ является отношением эквивалентности на V2-.
Доказательство оставляем в качестве упражнения.
Множество эквивалентных классов, определенное таким образом, обозначим через V2-/~. Каждый класс эквивалентности содержит ровно два элемента, так как если (v1, v2) V2-, то [(v1, v2)]={(v1, v2), (v2, v1)}. Здесь [(v1, v2)]— класс эквивалентности, содержащий (v1, v2).
Дадим строгое определение графа.
Определение. Графом G называется пара G = (V, E), где V —непустое конечное множество вершин, а Е — подмножество V2-/~
Другими словами, можно сказать, что граф G есть пара G = (V, Е), где V — непустое конечное множество вершин, а Е — множество неупорядоченных пар различных вершин.
Множество Е называют множеством ребер графа, |V| обозначает число вершин G, |Е| —число ребер G.
Следующий результат выражает связь между графами и классами отношений на конечных множествах.
Утверждение.
а) Граф G = (V, E) определяет нерефлексивное симметричное отношение на V.
б) Нерефлексивное симметричное отношение на конечном множестве V определяет граф.Доказательство.
а) Пусть G=(V, E) — граф. Определим отношение R(E) на V следующим образом: v1R(E)v2 тогда и только тогда, когда [v1, v2] E, Отношение R(E) нерефлексивно, так как vR(E)v тогда и только тогда,
когда [v, v] E, но [v, v] E, поскольку(v, v) V2 . R(E) симметрично
—
для v1R(E)v2 тогда и только тогда, когда [v1, v2] E, однако
Достарыңызбен бөлісу: |