Question

Скільки компонент зв’язності у графа G = (V, E), де V = {1, 2, 3, 4, 5, 6, 7, 8}, E = {12, 13, 24, 34, 48, 58, 67}?

а)1
б)2
в)3
г)4

Answer 1

Ответ:

в)3

Пошаговое объяснение:

Компонентою зв’язності у графі називається така максимальна підмножина вершин, що між будь-якими двома вершинами цієї підмножини існує шлях. Щоб знайти кількість компонент зв’язності у графі, можна використати алгоритм пошуку в глибину або в ширину, який перебирає всі вершини графа і визначає, до якої компоненти зв’язності вони належать.

У даному графі G = (V, E), де V = {1, 2, 3, 4, 5, 6, 7, 8}, E = {12, 13, 24, 34, 48, 58, 67}, можна виділити три компоненти зв’язності:

{1, 2, 3, 4}, яка містить вершини 1, 2, 3 і 4 і ребра між ними: 12, 13, 24 і 34.{5, 8}, яка містить вершини 5 і 8 і ребро між ними: 58.{6, 7}, яка містить вершини 6 і 7 і ребро між ними: 67.

Ось приклад графічного зображення цього графа:

![Граф G]

Тому правильною відповіддю на питання є в) 3.