Перелік графів - Студопедія

Завдання

1.1. Граф заданий безліччю вершин та безліччю ребер

. Намалюйте цей граф, збудуйте для нього матриці

суміжності та інцидентності, списки суміжності.

1.2. Побудуйте матрицю інцидентності для графа, заданого списками суміжності:

1.3. У графі 30 вершин і 80 ребер кожна вершина має ступінь 5 або 6. Скільки в ньому

вершин ступеня 5?

1.4. У графі кожна вершина має ступінь 3, число ребер укладено між 16 і 20.

Скільки вершин у цьому графі?

1.5. Знайдіть усі абстрактні графи з 4 вершинами.

1.6. Знайдіть усі абстрактні графи з набором ступенів а) (2,2,2,3,3,4);

1.7. Відновіть граф за його

а) породженим підграфам, отриманим видаленням однієї вершини:

б) остовним подграфам, отриманим видаленням одного ребра:

1.8. Граф маєnвершин іmребер. Скільки в нього різних а) кістяків;

б) породжених підграф?

1.9. 1) Подайте граф як об'єднання трьох графів з безліччю вершин

2) Чи правильно, що будь-який граф з 6 вершинами можна представити як об'єднання трьох

графів з такими множинами вершин?

3) Чи вірно, що будь-який граф з 6 вершинами можна подати як об'єднання трьох

1.10. Чи правда, що для будь-яких графів і виконується рівність

?

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

зв'язкові.

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

нескладні.

1.13. Чи ізоморфні графи 1) і ; 2) і; 3) та ?

1.14. Знайдіть граф з мінімальним числом вершин, який не є сумою

чи з'єднанням менших графів.

1.15. Граф заданий матрицею суміжності:

вершинами
.

Побудуйте для нього матрицю відстаней між вершинами, знайдіть

ексцентриситети вершин, діаметр, радіус, центр. Чи ізоморфні цей граф і

додатковий до нього?

1.16. Яка відстань між вершинами (0,0.0) та (1,1.1) у графі? Скільки

є найкоротших шляхів між цими вершинами?

1.17. Який найбільший діаметр може мати граф з вершинами? Скільки є

(абстрактних) графів із таким діаметром?

1.18. Знайдіть усі (з точністю до ізоморфізму) графи з 5 вершинами діаметра 3.

1.19. Чи може радіус графа в результаті додавання одного нового ребра: а) збільшитися;

б) зменшитись; в) залишитися тим самим?

1.20. Знайдіть усі (з точністю до ізоморфізму) графи з 5 вершинами радіусу 1.

1.21. Знайдіть усі (з точністю до ізоморфізму) графи з 4 вершинами, що мають точно

одну центральну вершину.

1.22. Побудуйте граф перетинів а) граней тривимірного куба; б) ребер графа.

1.23. Скільки ребер у графі перетинів ребер графа?

1.24. Граф перетинів сімейства інтервалів прямою називають графом інтервалів.

Які з наступних графів є графами інтервалів: , , , , ,

,?

1.25. Граф перетинів сімейства дуг кола називають графом дуг. Які з

графи попереднього завдання є графами дуг?

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно