2015-07-21
1765
1. Задати прості графи за допомогою матриць інцидентності та суміжності.
2. Задати орієнтовані графи за допомогою матриць інцидентності та суміжності.
3. Зобразити неорієнтовані графи за матрицями суміжності:
4. Чи є будь-яка квадратна симетрична (0,1)-матриця, що містить 0 на головній діагоналі, матрицею суміжності якогось простого графа?
5. Зобразити орієнтовані графи за матрицями інцидентності:
6. Зобразити неорієнтований граф, заданий множиною вершин і багатозначним відображенням Г.
| 
| 
| 
| 
| 
|
| 
|
| 
| 
| 
|
7. Зобразити орієнтований граф, заданий множиною вершин і багатозначним відображенням Г.
|
|
|
|
|
|
|
|
| 
| 
| 
| 
| 
|
8. Знайти матриці суміжності для графів: а) 
; в) 
; в) 
; г) 
; д) 
?
9. Нехай 
– простий граф. Нагадаємо, що доповнювальним називають такий граф 
, у якого та сама множина вершин і дві вершини в з'єднано ребром тоді й лише тоді, коли їх не з'єднано ребром у графі . Знайти:
а) 
; б) 
; в) 
?
10. Нехай – простий граф з 
вершинами та 
ребрами. Довести, що об'єднання та утворює граф
|
|
|
11. Простий граф має 15 ребер, а граф –13. Знайти кількість вершин графа .
12. Простий граф має вершин і ребер. Знайти кількість ребер графа .
13. Знайдіть матриці інцидентності та матриці суміжності графів:
а) 
б) 
в) 
г) 
д) 
е) 
є) 
ж) 
14. Для заданих матриць інцидентності знайдіть відповідні графи:
а) 
б) 
15. Для заданих матриць суміжності знайдіть відповідні графи:
а) 
б) 
16. Для графів, зображених на мал. 1, 2, 3, 4,
a) знайдіть матрицю суміжності;
b) використовуючи матрицю суміжності, знайдіть всі шляхи довжини 2;
c) використовуючи матрицю суміжності, знайдіть всі шляхи довжини 3.
Мал. 1 Мал. 2 Мал. 3 Мал. 4
17. Матриці інцидентності для мультиграфів можна визначити таким же способом, як і для звичайних графів. Як по матриці інцидентності можна судити про те, чи мають два ребра мультиграфа спільні вершини? (Такі ребра називаються кратними)
18. Якщо розглядається матриця інцидентності для мультиграфа, чи дає сума елементів рядка, позначеного даною вершиною, ступінь даної вершини? Що означає сума елементів рядка?
19. Який з орграфів є зв'язним? Який з них є сильно зв'язним? Для кожного графа знайдіть, якщо можливо, орієнтований шлях довжини 2, орієнтований шлях довжини 3, орієнтований шлях довжини 4 і орієнтований шлях довжини 5.
а) 
б) 
в) 
г) 
д) 
е) 
є) 
ж) 
20. Які з наступних графів є сильно зв'язними?
а) 
б) 
в) 
г) 
д) 
е) 
21. Знайдіть діаметр наступних графів:
а) ; б) ;
в) 
; г) 
; д) 
;
е) 
; е) 
; ж) 
