Підсумковий тест "Теорія графів"

Що таке граф у дискретній математиці?

Як називається вершина графа, степінь якої дорівнює 0?

Степенем вершини називається...

Граф, у якому кожне ребро має напрямок, називається:

Як називається ребро, що з'єднує вершину саму з собою?

Чому дорівнює сума степенів усіх вершин графа?

Згідно з лемою про рукостискання, кількість вершин з непарним степенем завжди повинна бути:

Повним графом називається граф, у якому:

Граф, який не містить циклів і є зв'язним, називається:

Скільки ребер має дерево з n вершинами?

Шлях, у якому перша і остання вершини збігаються, називається:

Матриця суміжності — це квадратна матриця, де елемент a_ij дорівнює 1, якщо:

Яка властивість матриці суміжності для неорієнтованого графа?

Цикл, що проходить через кожне ребро графа рівно один раз, називається:

Для того, щоб зв'язний неорієнтований граф мав Ейлерів цикл, необхідно і достатньо, щоб:

Цикл, що проходить через кожну вершину графа рівно один раз, називається:

Як називається підграф, який є деревом і містить усі вершини вихідного графа?

Відстанню між двома вершинами у графі називається:

Найбільша з відстаней від даної вершини до інших вершин графа називається:

У зваженому графі кожному ребру приписано число, яке називається:

Яка максимальна кількість ребер у простому неорієнтованому графі з n вершинами?

Вершина дерева зі степенем 1 називається:

Граф називається незв'язним, якщо:

Яка кількість компонент зв'язності у зв'язного графа?

Як називається ребро, видалення якого збільшує кількість компонент зв'язності?

Вершина, видалення якої (разом з інцидентними ребрами) збільшує кількість компонент зв'язності, називається:

Дерево — це граф, у якому будь-які дві вершини з'єднані:

Що вивчає теорія графів?

Граф без ребер називається:

Матриця інцидентності описує зв'язок між:

Дано граф з 6 вершинами. Степені п'яти вершин дорівнюють: 3, 2, 4, 1, 5. Яким може бути степінь шостої вершини?

У матриці суміжності простого неорієнтованого графа сума елементів у третьому рядку дорівнює 4. Що це означає?

Чи існує простий граф, у якому 5 вершин мають степені: 4, 4, 3, 2, 1?

Дано дерево, яке має 15 вершин. Скільки ребер у цьому дереві?

При побудові остова (кістякового дерева) для зв'язного графа з 10 вершинами та 20 ребрами, скільки ребер доведеться видалити?

Яка з наведених послідовностей степенів вершин відповідає повному графу K₄?

Граф має 10 вершин і складається з 3 окремих компонент зв'язності, кожна з яких є деревом. Скільки всього ребер у такому графі (лісі)?

Дано граф

Знайти:

1. діаметр графа

2. радіус графа

Установіть відповідність між поняттями та їхніми характеристиками .

Встановіть відповідність між назвою об'єкта та його визначальною властивістю.

Вам потрібно спроектувати мережу з 10 вузлів, яка є 'максимально стійкою до саботажу': видалення будь-яких 3 вершин не має розривати зв'язність. Яким має бути мінімальний степінь кожної вершини?