Учебник по дискретной математики. Д. Ушинского Дискретная математика

Основные определения и примеры графов.

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 отрезков так, чтобы каждый пересекался ровно с тремя другими?
   
8. 
   В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
   
9. 
   В группе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этой группе), 11 - по 4 друга, а 10 - по 5 друзей?
   
10. 
    В некоторой стране 19 регионов. Может ли оказаться так, что у каждого региона 1, 5 или 9 соседних регионов?
    
11. 
    В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
    
12. 
    Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
    
13. 
    В розыгрыше первенства по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
    
14. 
    Нарисуйте полный граф с n вершинами, если:
    

15. 
    Какова степень каждой вершины полного графа, у которого n вершин?
    
16. 
    Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В соревновании с двенадцатью участниками провели все встречи. Сколько было сыграно встреч?
    
17. 
    Может ли полный граф иметь 7, 8, 9, или 10 ребер?
    
18. 
    В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно перелететь, сделав не боле одной пересадки. Какое наибольшее число городов может быть в этом государстве?
    
19. 
    Какие из предложенных графов являются регулярными?
    

20. 
    В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.
    
21. 
    Известно, что в компании каждый человек знаком не менее, чем с половиной присутствующих. Докажите, что можно выбрать из компании четырех человек и рассадить их за круглым столом так, что при этом каждый будет сидеть рядом со своими знакомыми.
    
22. 
    Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч.
    
23. 
    Докажите, что в любом графе найдутся по крайней мере две вершины одинаковой степени
    

Матрицы, ассоциированные с графом

24. 
    Дана симметричная матрица размером n х n. В каждой строке расположено нечетное число единиц, остальные элементы равны нулю. Элементы на главной диагонали равны нулю. Доказать, что n является четным.
    
25. 
    Опишите матрицы смежности полных графов, вполне несвязных графов. Что можно сказать о матрице смежности простого графа и его дополнения?
    
26. 
    Изобразите матрицу смежности и инциденций графа:
    

27. 
    Изобразите матрицы смежности, инциденций графа:
    

28. 
    Дана матрица смежности. Изобразите граф, ей соответствующий.
    

    	1	2	3	4	5	6	7
    1	0	0	1	1	0	1	0
    2	0	0	0	0	1	0	1
    3	1	0	0	1	0	1	0
    4	1	0	1	0	1	0	1
    5	0	1	0	1	0	0	1
    6	1	0	1	0	0	0	0
    7	0	1	0	1	1	0	0

29. 
    Дана матрица инциденций. Изобразите граф, ей соответствующий.
    

	1	2	3	4	5
E1	1	0	0	0	1
E2	0	1	0	0	1
E3	0	0	0	1	1
E4	0	0	1	1	0
E5	0	0	1	0	1
E6	0	1	0	1	0
E7	1	0	1	0	0

30. 
    Установить, какие из следующих матриц являются матрицами смежностей простого графа, какие - матрицами инциденций и какие не являются ни теми, ни другими.