Условие:
Диаграмма неориентированного графа состоит из сторон правильного пятиугольника ABCDE и трех его диагоналей EB, CE, AD. Сколько ребер имеет подграф, порожденный множеством вершин \{A, E, D, B\} ?
Решение:
Нам дан неориентированный граф, построенный на правильном пятиугольнике ABCDE с его сторонами (AB, BC, CD, DE, EA) и тремя диагоналями (EB, CE, AD).
Нужно найти число ребер в подграфе, индуцированном множеством вершин {A, E, D, B}.
Шаг 1. Выпишем все ребра исходного графа.
• Стороны пятиугольника: – AB – BC – CD – DE – EA
• Диагонали: – EB – CE – AD
Шаг 2. Определим, ка...