Дискретная математика

169 11. Пусть граф состоит из вершин и ребер четырехмерного куба. Сколько вершин и сколько ребер имеет этот граф? 12. Используя принцип Дирихле, докажите, что если граф G имеет более одной вершины, то у него найдутся, по крайней мере, две вершины одинаковой степени. 13. Изоморфны ли графы, представленные на следующем рисунке? 14. Изоморфны ли графы, представленные на следующем рисунке? 15. Изоморфны ли графы, представленные на следующем рисунке? 16. На следующем рисунке даны графы, представленные своими диаграммами. Определите, изоморфны ли эти графы. ч N Ч 17. Постройте однородный (регулярный) граф степени 3 с 4 вершинами; с б вершинами; с 8 вершинами. Можно ли построить однородный граф степени 3 с 5 вершинами? 18. Пусть дан граф G, представленный на рис. 5.29. Постройте для G: а) матрицу смежности; б) матрицу инцидентности. 19. Логическая матрица смежности орграфа О имеет вид: И Л М = Л Л Л {И Л Л Л и л л л и л Вычислите М'' иМ \ Найдите матрицу достижимостиМ.