«Лабораторная работа 5. Графы. Вариант 1 »,
Информатика в Санкт-Петербурге

Лабораторная работа 5. Графы. Вариант 1 Задана таблица некоторого графа без весов (X -> Y, где X - номер строки в таблице, Y - номер столбца). Не изображая сам граф, определите: A) Степень каждой вершины (входящие и выходящие ребра) Б) Приведите пример "двусторонних" и "односторонних" рёбер В) Есть ли у графа петли Г) Какая вершина не связана с остальными Д) Перечислите вершины пути от А до Н Е) Изобразите подграф с вершинами B, C, G, E Сопоставьте вершины графа со строками и столбцами таблицы. Решение: А) Степень каждой вершины (входящие и выходящие ребра) A: входящие - 0, выходящие - 0, степень = 0 B: входящие - 0, выходящие - 0, степень = 0 C: входящие - 0, выходящие - 0, степень = 0 D: входящие - 0, выходящие - 0, степень = 0 E: входящие - 1, выходящие - 0, степень = 1 F: входящие - 1, выходящие - 0, степень = 1 G: входящие - 1, выходящие - 0, степень = 1 H: входящие - 1, выходящие - 0, степень = 1 Б) Примеры рёбер: Односторонние ребра: из Е, F, G, H в A, B, C, D Двусторонних ребер нет В) Петли: петель нет Г) Не связанные вершины: A, B, C, D не связаны с остальными Д) Перечислите вершины пути от А до Н: Пути от A до H нет Е) Изобразите подграф с вершинами B, C, G, E: B C G E Сопоставление вершин графа со строками и столбцами таблицы: ?1: 40 ?2: 40, 15 ?3: 35 ?4: 15, 35 ?5: 10 ?6: 48, 65, 22, 50 ?7: 11, 33, 40