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

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

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

37. Изобразите матрицу достижимости графа.

38.

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

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

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

41. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).

42. Докажите, что граф с n вершинами, степень каждой из которых не менее (n–1)/2- связен.

43. В некотором государстве лишь один вид транспорта – автомобиль. Из столицы выходит 21 автомобильная дорога, из города Дальний - одна, а из всех остальных городов - по 20. Докажите, что из столицы можно доехать в Дальний (возможно, с пересадками).

44. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.

45. Докажите, что если в графе все вершины имеют четную степень, то в графе нет ребра, удаление которого приводит к увеличению количества компонент связности.

46. В одной стране каждая пара городов соединена только одним транспортным маршрутом: или железнодорожным, или автобусным. Докажите, что существует вид транспорта, которым можно доехать из любого города страны в любой другой (возможно, с пересадками)

47. Докажите, что либо сам граф, либо дополнение к нему является связным.

48. На конференции по новым информационным технологиям студент Иванов познакомился с 52 студентами из разных городов России. По окончании конференции некоторые пары студентов обменялись адресами, причем у каждого из участников конференции оказалось не менее 26 адресов. Через некоторое время Иванову понадобилось узнать адрес студента Петрова, который также участвовал в конференции. Докажите, что Иванов может узнать адрес Петрова.

49. Каждый из семи мальчиков имеет не менее трех братьев. Докажите, что все мальчики – братья.

Дата добавления: 2014-12-29