Составители:
Рубрика:
63
Задачи по теории графов
Основные определения и примеры графов.
1. В шахматном турнире по круговой системе участвуют семь студентов. Известно, что
Ваня сыграл шесть партий, Толя – пять, Леша и Дима –по три, Семен и Илья – по две,
Женя - одну. С кем сыграл Леша?
2.
Покажите, что следующие объекты можно рассматривать как графы:
· вершины и ребра многогранника;
· план лабиринта;
·
дружеские отношения в группе студентов;
·
генеалогическое дерево;
· теннисный турнир;
· страны на карте.
3. На рисунке изображены молекулы этилена и бензола; через С и Н обозначены атомы
углерода и водорода соответственно. Можно ли считать эти диаграммы графами? Если
да, то что будет являться необходимым условием, для того чтобы граф представлял собой
молекулу какого-либо углеводорода?
4. Могут ли степени вершины в простом графе быть равны:
•
8, 6, 5, 4, 4, 3, 2, 2;
•
7, 7, 6, 5, 4, 2, 2, 1;
•
6, 6, 6, 5, 5, 3, 2, 2.
5. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число
рукопожатий, четно.
6.
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы
каждый телефон был соединен ровно с пятью другими?
7.
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с
тремя другими?
С
Н
Н
Н
Н
С
С
Н
Н
Н
Н
Н
Н
С
С
С
С
С
С
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
