27.Найти связь между матрицей смежности графа и матрицей смежности его дополнения.
Поскольку граф-дополнение создается из несмежных сторон графа, то матрица смежности графа-дополнения будет являться инверсией матрицы смежности обычного графа.
28. Найдите диаметр n – мерного куба.
Диаметр графа – наибольшее расстояние между двумя его вершинами.
Так как диаметром произвольного графа, а в нашем случае n-мерного куба, называется наибольшее расстояние между любыми двумя вершинами графа => n-мерный куб является связным графом диаметра n.
Отсюда следует, что из любой вершины такого куба, можно попасть в любую другую вершину, двигаясь по ребрам.
29. Найдите все простые цепи из вершины 6 в вершину 5.
30. Для двух графов выполняется свойство = . Найдите граф .
Тк. = => = , либо является линией.
31. Постройте граф , двойственный по отношению к заданному графу, представленному множеством ( набором ребер). В фигурных скобках указаны пары чисел. Это номера вершин, соединенных ребрами. Для двойственного графа определите число ребер, число вершин и число граней.
1){{1,2},{1,3},{1,5},{1,6}.{1,7},{2,3},{3,4},{3,5},{4,5},{4,7},{5,6},{6,7}};
2) {{1,3},{1,7},{2,3},{2,4}.{2,6},{2,7},{2,8},{3,5},{3,6},{4,5},{4,6},{6,7}.{7,8}};
3) {{1,3},{1,6},{2,3},{2,5},{2,8},{3
,4},{3,8},{4,8},{5,6},{5,7},{5,8},{6,7}};
Достарыңызбен бөлісу: |
