Установить соответствие 1. Подграф, порождённый вершинами v_1, v_2, v_3, v_4 2. Остовное дерево 3. Остовной подграф

Предмет: Математика
Раздел: Теория графов

Дано: граф G = \langle V = \{v_1, v_2, v_3, v_4, v_5\}, E = \{(v_1, v_2), (v_1, v_5), (v_2, v_3), (v_2, v_5), (v_3, v_4), (v_3, v_5), (v_4, v_5)\} \rangle и три подграфа, нужно установить соответствие:

1. Подграф, порождённый вершинами v_1, v_2, v_3, v_4
2. Остовное дерево
3. Остовной подграф

Шаг 1. Подграф, порождённый вершинами v_1, v_2, v_3, v_4

Подграф, порождённый вершинами, содержит все рёбра исходного графа, у которых обе вершины принадлежат множеству \{v_1, v_2, v_3, v_4\}. Рассмотрим ребра:

• (v_1, v_2) — обе вершины в множестве
• (v_2, v_3) — обе вершины в множестве
• (v_3, v_4) — обе вершины в множестве
• (v_1, v_5) — v_5 нет в множестве
• (v_2, v_5) — v_5 нет в множестве
• (v_3, v_5) — v_5 нет в множестве
• (v_4, v_5) — v_5 нет в множестве

Значит, подграф порождённый вершинами v_1, v_2, v_3, v_4 содержит вершины v_1, v_2, v_3, v_4 и рёбра (v_1, v_2), (v_2, v_3), (v_3, v_4). Это соответствует подграфу 3 (на рисунке подграф 3).

Шаг 2. Остовное дерево

Остовное дерево — это связный ацикличный подграф, содержащий все вершины исходного графа V = \{v_1, v_2, v_3, v_4, v_5\}, и минимальное количество рёбер (|V| - 1 = 4 ребра).

Рассмотрим подграфы:

• Подграф 1: содержит все вершины v_1, v_2, v_3, v_4, v_5 и рёбра (v_1, v_2), (v_1, v_5), (v_4, v_3), (v_5, v_4). Это 4 ребра, граф связный и без циклов — подходит под определение остовного дерева.

• Подграф 2: содержит все вершины, но рёбра (v_1, v_5), (v_5, v_3), (v_4, v_3). Рёбра 3, что меньше необходимого для остовного дерева.

Значит, подграф 1 — это остовное дерево.

Шаг 3. Остовной подграф

Остовной подграф — это связный подграф, включающий все вершины графа (как и остовное дерево), но может содержать циклы (не обязательно дерево).

Подграф 2 содержит все вершины, но у него 3 ребра, граф связный, но не дерево (так как меньше рёбер, чем нужно для дерева). Подграф 2 — остовной подграф (связный, содержит все вершины).

Итоговое соответствие:

• Подграф, порождённый вершинами v_1, v_2, v_3, v_4 — подграф 3
• Остовное дерево — подграф 1
• Остовной подграф — подграф 2

Если нужна помощь с выбором в интерфейсе, то:

• Для "подграф, порождённый вершинами v_1, v_2, v_3, v_4" выбрать "подграф 3"
• Для "остовное дерево" выбрать "подграф 1"
• Для "остовной подграф" выбрать "подграф 2"