Практичне заняття №12. Поняття про графи

1. Знайти кількість вершин, ребер і степені кожної вершини неорієнтованих

графів:

а) б)

2. Знайти суму степенів вершин кожного з графів задачі 1 та переконатись, що вона вдвічі більша за кількість ребер графа.

3. Визначити кількість вершин та дуг і знайти напівстепені входу й виходу для кожної вершини орієнтованих графів:

а) б)

4. Для кожного з графів задачі 3 знайти суму напівстепенів входу та суму напівстепенів виходу вершин. Переконатись, що кожна з них дорівнює кількості дуг графа.

5. Побудувати графи:

а) К₇; б) К_1,8; в) К_1,4; г) К_3,4; д) С₇; е) ; є)

6. Які з наведених нижче графів дводольні?

7. Для яких значень наведені нижче графи дводольні: а) ; в) ; в) ; г) ?

8. Скільки вершин і ребер мають наведені нижче графи: а) ; в) ; в) ; г) ; д) ?

9. Скільки ребер має граф, у якого вершини мають такі степені: 4, З, З, 2, 2? Зобразити його.

10. Чи існує простий граф із вершинами таких степенів? Якщо так, то зобразити його:

а) З, З, З, З, 2; б) 3, 4, 3, 4, 3; в) 1, 2, 3, 4, 5;

г) 1, 2, 3, 4, 4; д) 0, 1, 2, 2, 3; є) 1, 1, 1, 1, 1.

11. Нехай – граф з вершинами та ребрами. Нехай – максимальний степінь вершини цього графа, а – мінімальний. Довести, що .

12. Що з переліченого нижче є шляхом у графі на мал. 1. Які з них є простими шляхами? Вкажіть довжину кожного шляху.

мал. 1

a) ;

b) ;

c) ;

d) .

13. Що з переліченого нижче є шляхом у графі на мал. 2. Які з них є простими шляхами? Вкажіть довжину кожного шляху.

мал. 2

a) ;

b) ;

c) ;

d) .

14. Знайдіть вершини й орієнтовані ребра для орграфів. Для кожної вершини визначте степінь входу й степінь виходу. Для кожного графа побудуйте чотири підграфа.

а) б) в) г)

д) е) є) ж)

з) и) і) ї)