Учебник по дискретной математики. Д. Ушинского Дискретная математика

• Название: Д. Ушинского Дискретная математика
• Анкор: Учебник по дискретной математики.doc
• Дата: 20.05.2017
• Размер: 2.66 Mb.
• Имя файла: Учебник по дискретной математики.doc
• Тип: Документы; #8001
• страница: 15 из 20

Изоморфизм графов

31. 
    Являются ли изоморфными графы? Ответ обосновать.
    

32. 
    Докажите, что графы являются изоморфными.
    

33. 
    Докажите, что графы являются изоморфными.
    

34. 
    Докажите, что графы не изоморфны.
    

35. 
    Докажите, что графы не изоморфны.
    

Достижимость и связность.

36. 
    Дана матрица смежности графа. Не изображая граф, ответьте на следующие вопросы:
    

• 
  Какова степень пятой вершины? Назовите смежные с ней вершины.
  
• 
  Существует ли путь из вершины 2 в вершину 8?
  

	1	2	3	4	5	6	7	8
1	0	1	1	0	0	0	0	0
2	1	0	0	0	0	0	0	0
3	1	0	0	1	0	0	0	1
4	0	0	1	0	0	0	0	0
5	0	0	0	0	0	1	1	0
6	0	0	0	0	1	0	1	0
7	0	0	0	0	1	1	0	0
8	0	0	1	0	0	0	0	0

37. 
    Изобразите матрицу достижимости графа.
    
38. 
    Д
    ана матрица смежности графа. Найти все вершины, входящие в одну компоненту связности с вершиной 7.
    

    	1	2	3	4	5	6	7	8	9	10
    1	0	1	1	0	0	0	0	0	0	0
    2	1	0	1	0	0	0	0	0	0	0
    3	1	1	0	0	0	0	0	0	0	0
    4	0	0	0	0	1	0	1	0	0	0
    5	0	0	0	1	0	1	0	0	0	0
    6	0	0	0	0	1	0	1	0	0	0
    7	0	0	0	1	0	1	0	0	0	0
    8	0	0	0	0	0	0	0	0	1	1
    9	0	0	0	0	0	0	0	1	0	1
    10	0	0	0	0	0	0	0	1	1	0

39. 
    Выделите компоненты связности графа
    

0	1	1	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	1	1
0	0	0	0	1	0	1
0	0	0	0	1	1	0

0	1	0	0	0	0	0
1	0	0	0	0	0	0
0	0	0	1	0	0	0
0	0	1	0	0	0	0
0	0	0	0	0	1	1
0	0	0	0	1	0	1
0	0	0	0	1	1	0

0	0	0	0	1	1	0
0	0	0	0	1	1	0
0	0	0	1	0	0	1
0	0	1	0	0	0	1
1	1	0	0	0	0	0
1	1	0	0	0	0	0
0	0	1	0	0	0	0

40. 
    Дана матрица смежности графа. Найдите матрицу достижимостей этого графа, не изображая его.
    

    	1	2	3	4	5	6	7	8	9
    1	0	0	0	1	0	0	1	0	0
    2	0	0	1	0	0	0	0	0	0
    3	0	1	0	0	0	0	0	0	0
    4	1	0	0	0	0	0	1	0	0
    5	0	0	0	0	0	1	0	1	1
    6	0	0	0	0	1	0	0	1	1
    7	1	0	0	1	0	0	0	0	0
    8	0	0	0	0	1	1	0	0	1
    9	0	0	0	0	1	1	0	1	0

41. 
    В стране Семерка 15 городов, каждый из которых соединен дорогами не менее чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).
    
42. 
    Докажите, что граф с n вершинами, степень каждой из которых не менее (n–1)/2- связен.
    
43. 
    В некотором государстве лишь один вид транспорта – автомобиль. Из столицы выходит 21 автомобильная дорога, из города Дальний - одна, а из всех остальных городов - по 20. Докажите, что из столицы можно доехать в Дальний (возможно, с пересадками).
    
44. 
    В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
    
45. 
    Докажите, что если в графе все вершины имеют четную степень, то в графе нет ребра, удаление которого приводит к увеличению количества компонент связности.
    
46. 
    В одной стране каждая пара городов соединена только одним транспортным маршрутом: или железнодорожным, или автобусным. Докажите, что существует вид транспорта, которым можно доехать из любого города страны в любой другой (возможно, с пересадками)
    
47. 
    Докажите, что либо сам граф, либо дополнение к нему является связным.
    
48. 
    На конференции по новым информационным технологиям студент Иванов познакомился с 52 студентами из разных городов России. По окончании конференции некоторые пары студентов обменялись адресами, причем у каждого из участников конференции оказалось не менее 26 адресов. Через некоторое время Иванову понадобилось узнать адрес студента Петрова, который также участвовал в конференции. Докажите, что Иванов может узнать адрес Петрова.
    
49. 
    Каждый из семи мальчиков имеет не менее трех братьев. Докажите, что все мальчики – братья.