Кружок 6 класса
Руководитель Евгений Александрович Асташов
2012/2013 учебный год
Занятие 18. Графы
Знакомство с графами
- 1.
-
Волшебная страна Фарг почти вся состоит из непреодолимых гор и рек. В ней есть шесть городов: А, Б, В, Г, Д и Е.
Известно, что из А проложены дороги в Б и Г, из Б — в А, Г и Д, из В — в Г и Е, из Г — в В и Д, из Д — в Б и Г, из Е — только в В.
Все остальные дороги непроходимы.
- а)
- Нарисуйте карту страны Фарг.
- б)
- Нарисуйте карту так, чтобы дороги не пересекались.
- в)
- Может ли житель города А попасть в город Д, если ему нельзя проходить через Г?
- г)
- Сможет ли он при тех же условиях попасть в город Е?
Будем называть графом набор точек (вершин), некоторые из которых соединены между собой линиями (рёбрами). Граф называется связным,
если от любой его вершины можно по рёбрам добраться до любой другой (и несвязным иначе). Степенью вершины называется число выходящих из нее ребер.
Два графа будем называть одинаковыми, если выполнены следующие два условия:
-
у них равное число вершин;
-
вершины каждого графа можно пронумеровать так, что если вершины с номерами i и j соединены ребрами в одном графе, то вершины с теми же номерами соединены
таким же числом рёбер и в другом графе, а если вершины с номерами i и j не соединены ребром в одном графе,
то вершины с теми же номерами не соединены и в другом графе.
- 2.
-
Найдите все наборы одинаковых графов:
- 3.
-
Найдите количество:
- а)
- графов с двумя вершинами;
- б)
- графов с тремя рёбрами;
- в)
- связных графов с тремя рёбрами;
- г)
- несвязных графов с четырьмя вершинами.
- 4.
-
Можно ли начертить данные графы одним росчерком (не отрывая руки от бумаги и не проходя по ребру дважды)?
- 5.
-
Докажите, что граф с более чем двумя вершинами нечётной степени невозможно начертить одним росчерком (не отрывая ручки от бумаги и не проводя никакое ребро дважды).
- 6.
-
Дана проволока длиной 12 см. Можно ли сложить из нее каркас куба с ребром в 1 см? Проволоку нельзя резать.
Разные задачи
- 7.
-
Докажите, что среди любых шести человек обязательно найдутся либо три попарно знакомых, либо три попарно незнакомых.
- 8.
-
Пешеход обошел шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь один раз. Могло ли такое быть, если в городе нет тупиков?
