Сформулируйте задачу в терминах теории графов (1 балл)

Собеседование по теме «введение в теорию графов»

1. Дайте определение следующих терминов (1 балл)

a. Граф

b. Ориентированный и неориентированный граф

c. Ребро

d. Дуга

e. Грань

f. Смежные вершины

g. Степень вершины

h. Регулярный граф

i. Полный граф

j. Двудольный граф

k. Полный двудольный граф

l. Изоморфные графы

m. Маршрут

n. Цикл

o. Эйлеров цикл

p. Гамильтонов цикл

q. Связный граф

r. Компонента связности графа

s. Сильно связный ориентированный граф

t. Дерево, лес

u. Цикломатическое число графа

v. Остов (каркас, стягивающие дерево)

w. Остов минимального веса

x. Планарный граф

y. Элементарное стягивание

z. Двойственный граф

aa. Раскраска графа, правильная раскраска графа

bb. Хроматическое число

Приведите пример (1 балл)

a. Регулярного графа

b. Полного графа

c. Изоморфных графов

d. Связного и несвязного графа

e. Эйлерового графа

f. Гамильтонова графа

g. Двудольного графа

h. Полного двудольного графа

i. Планарного графа

j. Графа и двойственного ему графа

k. Двураскрашиваемого графа

 

Сформулируйте условие теорем: (1 балл)

1. Лемма о рукопожатиях.
2. Орлемма о рукопожатиях.
3. Необходимое и достаточное условие того, что неориентированный граф эйлеров.
4. Необходимое и достаточное условие того, что ориентированный граф эйлеров.
5. Теорема Дирака.
6. Свойства деревьев.
7. Необходимое и достаточное условие того, что граф двудольный.
8. Теорема Холла.
9. Формула Эйлера.
10. Теорема о пяти красках.

Докажите теорему

a. Из вопроса 3 (баллы: 1, 1, 1, 1, 3, 1, 2, 3, 2, 3)

b. Любой турнир полугамильтонов (3 балла)

c. Любой сильно связный турнир гамильтонов (3 балла)

d. Граф К₅ – не планарен (2 балла)

e. Граф К_3,3 – не планарен (2 балла)

f. В любом связном графе с 2к нечетными вершинами можно указать семейство из к путей, которые в совокупности содержат все ребра графа по одному разу (2 балла)

g. В любом плоском графе найдется вершина степень которой не больше 5. (2 балла)

Изобразите матрицу смежности графа (1 балл)

	а)		б)		с)

 

 

Изобразите матрицу инцидентности графа из задания 5 ((1 балл))

Изобразите матрицу достижимости графа из задания 5, из задания 9 (1 балл)

Изобразите граф заданный матрицей смежности (9 задание) (1 балл)

Выделите компоненты связности графа (2 балла)

 

 

 

Постройте каркас минимального веса для графа заданного матрицей весов (2 балла)

		¥	¥	¥		¥
		¥	¥		¥
¥	¥				¥
¥	¥				¥
¥						¥
	¥	¥	¥			¥
¥				¥	¥

 

		¥	¥	¥
			¥	¥
¥				¥	¥	¥
¥	¥					¥
¥	¥	¥				¥
		¥
	¥	¥	¥	¥

 

	¥	¥	¥	¥
¥			¥	¥		¥
¥			¥	¥		¥
¥	¥	¥				¥
¥	¥	¥				¥
	¥	¥	¥	¥

 

Определите, является ли граф, заданный матрице смежности, эйлеровым. (1 балл)

Найдите правильную раскраску вершин графа (1 балла)

		с)
	а)		б)

Выделите компоненты сильной связности графа (2 балла)

		б)
	а)

Сформулируйте задачу в терминах теории графов (1 балл)

a) В группе 30 человек. Может ли быть так, что 5 из них имеют по 3 друга (в этой группе), 7 - по 4 друга, а 18 - по 5 друзей?

b) В некоторой стране 29 регионов. Может ли оказаться так, что у каждого региона 1, 3 или 7 соседних регионов?

c) В государстве 200 городов, и из каждого из них выходит 5 дорог. Сколько всего дорог в государстве?

d) Может ли в государстве, в котором из каждого города выходит 5 дорог, быть ровно 102 дороги?

e) Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В соревновании с двенадцатью участниками провели все встречи. Сколько было сыграно встреч?

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

g) На конференции присутствуют 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.

h) В мафиозной группировке связь налажена так, что главарь может связаться напрямую с 19 членами мафии. Член мафии по прозвищу «Скрытый» может напрямую связаться только с одним коллегой. Остальные могут связаться ровно с 20 коллегами. Доказать, что главарь может передать сообщение Скрытому (возможно, через других своих подручных).

i) В группе четное число студентов. Некоторые студенты дружат между собой, причем известно, что каждый студент дружит не менее чем с половиной одногруппников. Докажите, что можно рассадить студентов за круглым столом так, что справа и слева от каждого будет сидеть друг.

j) В парке «Лотос» невозможно найти такой маршрут для прогулок по его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку содержит не более одного раза. Докажите, что некоторые дорожки парка приводят в тупик.

k) В стране 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

l) В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

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

n) 20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я - у 3-й,..., 19-я у 20-й.

o) Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, универсам. Сколько будет построено универсамов?

p) Инженер Иванов усовершенствовал свою плату. Теперь она имеет 9 приборов и 17 проводников. Схема платы представлена на рисунке. Можно ли изготовить такую плату так, что все проводники будут расположены на одной её стороне?

 

 

q) Образовавшийся коммерческий университет арендует здание для проведения занятий. В четверг проводится 7 лекций: право, английский язык, французский язык, экономика, менеджмент, маркетинг, этикет. Чтение каждой лекции в отдельности занимает один час, известно, что некоторые лекции не могут читаться одновременно. Опишите алгоритм, который определяет минимальное время, за которое могут быть почитаны лекции в четверг.