![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Упражнения. 4.1. Найти число ребер и степени вершин в полных графах К6, К7, К8.4.1. Найти число ребер и степени вершин в полных графах К6, К7, К8. 4.2. Найти количество ребер в полных двудольных графах К4, 6, К3, 5, К2, 3. Составить матрицу связности графа К2, 3. 4.3. Найти количество ребер в графах Е2, Е3, Е4. Построить реализации графов Е2, Е3 (Е2, Е3, Е4 – двух-, трех-, четырехмерные кубы). 4.4. Найти число полных трехвершинных подграфов в полных двудольных графах К3, 5, К4, 3. 4.5. Количество ребер в однородном графе G равно 15. Степень каждой вершины графа равна 3. Найти количество вершин графа G. 4.6. Существует ли полный граф с семью ребрами? С 50 ребрами? 4.7. Дан полный граф G и "i: δ (v i) = 20. Найти количество вершин и ребер графа. 4.8. Доказать, что графы Е³, Е4 являются двудольными. 4.9. Найти дополнение графа G до полного графа. Составить матрицы смежности графа G и его дополнения (по формуле).
4.10. Для заданного графа G: а) Построить соответствующий реберный граф; б) Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа (по формуле); в) Определить степени вершин реберного графа через степени вершин исходного графа; г) Определить число ребер в реберном графе, используя исходный граф G:
4.11. Построить однородный 5-вершинный граф. Составить его матрицу инцидентности. По матрице инцидентности найти матрицу смежности однородного графа. Построить соответствующий реберный граф. Найти его матрицу смежности, степени вершин, число ребер, используя исходный однородный граф. § 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер) Определение: Путь (маршрут) в орграфе Д (графе G) из вершины vi в вершину vj (i Алгоритм поиска минимального пути из v в w орграфе Д (графе G). Введем обозначения: Пусть Д = (V, X) – орграф, v Обозначим Д(v) = {w Д-1(v) = {w Д(V1) = Д-1(V1) = Пусть G = (V, X) – граф, v Обозначим G(v) = {w G(V1) = Пусть Д = (V, X) – орграф с n вершинами (n v, w – заданные вершины из V, v Опишем алгоритм поиска минимального пути из v в w в орграфе Д (алгоритм фронта волны). 1. Помечаем вершину v индексом 0, т. е. F W0 (v) = { v }. Затем помечаем образы вершины v, индексом 1. Множество вершин с индексом 1 обозначим FW1(v). Полагаем k = 1. 2. Если FWk(v) = Ø или k = n – 1, w 3. Если w Последовательность вершин: v w1 w2 … wk-1w, где wk-1 wk-2 … w1 и есть искомый путь длины k из v в w. На этом работа алгоритма заканчивается. 4. Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем F Wk+1 (v). Присваиваем k := k+1 и переходим к шагу 2. Множество F W(v) в алгоритме обычно называют фронтом волны Вершины w1, …, wk-1 из последовательности (1), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.
|