Введение в теорию графов. Итоговый тест
Этот тест направлен на знание основных понятий о графах, а также на решение задач. Ключевые слова: путь в графе, длина пути, цикл графа, цепь графа.
Задание 1
Граф называется связным, если две любые вершины в этом графе соединены...
Задание 2
Замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются, называется...
Задание 3
Расстояние между вершинами есть...
Задание 4
Путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются, называется...
Задание 5
В городе N улиц, образующих сетку 5 x 5 (5 улиц идут с севера на юг, и 5 улиц — с запада на восток, всего 25 перекрёстков). Петя находится на перекрёстке в северо-западном углу города, а его друг Вася — на перекрёстке в юго-восточном углу города. Петя может двигаться только на юг или на восток. Какое минимальное количество перекрёстков должен проехать Петя, чтобы добраться до Васи (включая начальный и конечный перекрёстки)?
Задание 6
В стране Ландия 101 город, некоторые из них соединены дорогами. При этом любые два города соединяет ровно один маршрут. Сколько в этой стране дорог?
Задание 7
Если вершине инцидентна петля, то степень этой вершины равна...
Задание 8
В море живут осьминожки. У каждого из них или один, или два друга. Когда взошло солнце, те, у кого было двое друзей, посинели, а те, у кого один друг, покраснели, и оказалось, что любые два друга разноцветные. Однако друзья должны иметь одинаковый цвет, и поэтому 10 синих осьминожек перекрасились в красный цвет, а 12 красных — в синий. Сколько осьминожек живёт в море?
Задание 9
В графе каждая вершина окрашена в зелёный или синий цвет. Известно, что каждая синяя вершина соединена с 5 синими и 10 зелёными вершинами, а каждая зелёная — с 9 синими и 6 зелёными. Определите отношение количества синих и зелёных вершин.
Задание 10
Петя нарисовал несколько точек на плоскости так, что никакие три из них не лежат на одной прямой, и соединил каждые две точки отрезком. Сколько точек должен был нарисовать Петя, чтобы получилось ровно семь отрезков?