На каком из рисунков изображен граф, если степени вершин графа заданы следующим образом: y(A)=2, y(B)=4, y(C)=3

Тема: Поиск графа по степеням вершин

Пояснение: Для того чтобы определить, на каком из рисунков изображен граф, имея заданные степени вершин, мы можем использовать следующий подход. Сначала мы должны понять, какие вершины имеют наибольшую и наименьшую степень. Затем мы ищем вершину с наибольшей степенью и ассоциируем ей вершину с наименьшей степенью, чтобы установить связь между ними. При этом убираем эти две вершины из рассмотрения и продолжаем анализ с оставшимися вершинами.

Пример использования: Для данной задачи у нас имеются степени вершин графа: y(A)=2, y(B)=4, y(C)=3, y(D)=3, y(E)=4, y(F)=3, y(G)=2, y(H)=3. Сначала мы находим вершину с наибольшей степенью, это вершина B с степенью 4. Затем мы ищем вершину с наименьшей степенью, это вершина A с степенью 2. Связываем эти две вершины ребром и убираем их из рассмотрения. Оставшийся граф имеет следующие степени вершин: y(C)=3, y(D)=3, y(E)=4, y(F)=3, y(G)=2, y(H)=3. Продолжая анализ, находим вершину с наибольшей степенью E и связываем ее с вершиной наименьшей степени G. Итоговый граф будет иметь вид: B-A-E и вершины C, D, F, H будут иметь по 3 ребра.

Совет: Для более легкого определения графа по степеням вершин можно использовать схему решения и постепенно строить граф по мере нахождения связей между вершинами.

Упражнение: Найдите граф, если степени вершин заданы следующим образом: y(A)=3, y(B)=2, y(C)=4, y(D)=3, y(E)=2, y(F)=3, y(G)=2, y(H)=2.