Введение в теорию графов. Итоговый тест

Этот тест направлен на знание основных понятий о графах, а также на решение задач. Ключевые слова: путь в графе, длина пути, цикл графа, цепь графа.

Задание 1

Граф называется связным, если две любые вершины в этом графе соединены...

Задание 2

Замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются, называется...

Задание 3

Расстояние между вершинами есть...

Задание 4

Путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются, называется...

Задание 5

В городе N улиц, образующих сетку 5 x 5 (5 улиц идут с севера на юг, и 5 улиц — с запада на восток, всего 25 перекрёстков). Петя находится на перекрёстке в северо-западном углу города, а его друг Вася — на перекрёстке в юго-восточном углу города. Петя может двигаться только на юг или на восток. Какое минимальное количество перекрёстков должен проехать Петя, чтобы добраться до Васи (включая начальный и конечный перекрёстки)?

Задание 6

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

Задание 7

Если вершине инцидентна петля, то степень этой вершины равна...

Задание 8

В море живут осьминожки. У каждого из них или один, или два друга. Когда взошло солнце, те, у кого было двое друзей, посинели, а те, у кого один друг, покраснели, и оказалось, что любые два друга разноцветные. Однако друзья должны иметь одинаковый цвет, и поэтому 10 синих осьминожек перекрасились в красный цвет, а 12 красных — в синий. Сколько осьминожек живёт в море?

Задание 9

В графе каждая вершина окрашена в зелёный или синий цвет. Известно, что каждая синяя вершина соединена с 5 синими и 10 зелёными вершинами, а каждая зелёная — с 9 синими и 6 зелёными. Определите отношение количества синих и зелёных вершин.

Задание 10

Петя нарисовал несколько точек на плоскости так, что никакие три из них не лежат на одной прямой, и соединил каждые две точки отрезком. Сколько точек должен был нарисовать Петя, чтобы получилось ровно семь отрезков?