Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 28

Последовательность степеней простого графа — это последовательность степеней узлов в графе в порядке убывания. Какая из следующих последовательностей не может быть последовательностью степеней любого графа?

(I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1 

(А) I и II
(B) III и IV
(C) только IV
(D) II и IV

Ответ: (D)
Пояснение: универсальный алгоритм или метод для решения этого вопроса

1: процедура является alidDegreeSequence (L)

2: для n в списке L сделать

3: если L не имеет n элементов рядом с текущим, вернуть false

4: уменьшить число следующих n элементов списка на 1

5: расположите его как последовательность градусов, то есть в порядке убывания

6: если какой-либо элемент списка становится отрицательным, вернуть false

7: верните истину

Обоснование этого метода основано на свойствах простого графа. Перечисление возвращаемых значений: 1) если L не имеет достаточного количества элементов после текущего или 2) если какой-либо элемент списка становится отрицательным, то это означает, что не хватает узлов для размещения ребер простым графическим способом , что приведет к нарушению одного из двух условий простого графа (без самоконтроля и без кратных ребер между двумя узлами), если не других.

Смотри http://espressocode.top/data-structures-and-algorithms-set-25/

Это решение предоставлено Vineet Purswani.

Еще один:

Последовательность степеней d1, d2, d2. , , Неотрицательное целое число dn является графическим, если оно является степенной последовательностью графа. Теперь мы представим мощный инструмент, чтобы определить, является ли конкретная последовательность графической из-за Гавела и Хакими

Теорема Гавела – Хакими:

→ Согласно этой теореме, пусть D — последовательность d1, d2, d2. , , dn с d1 ≥ d2 ≥ d2 ≥. , , dn для n≥2 и di ≥ 0.

→ Тогда D0 — последовательность, полученная следующим образом:

→ Отказ от d1, и
→ Вычитая 1 из каждой из следующих d1 записей D.
→ То есть последовательность градусов D0 будет: d2-1, d2-1, d3-1. , , , дд1 + 1 -1. , , , дн
→ Тогда D является графическим тогда и только тогда, когда D0 является графическим.

Теперь мы применим эту теорему к заданным последовательностям:

вариант I) 7,6,5,4,4,3,2,1 → 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0 0,0 → 0,0,0,0, поэтому его графическое.

Вариант II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 (расположить в порядке возрастания) → 5,5,5,2,2,2 , 1 → 4,4,1,1,1,0 → 3,0,0,0,0 → 2, -1, -1, -1,0, но d (степень вершины) неотрицательна, поэтому ее не графический.

Вариант III) 7,6,6,4,4,3,2,2 → 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0 0,0 → 0,0,0,0, поэтому его графическое.

Вариант IV) 8,7,7,6,4,2,1,1, здесь степень вершины равна 8, а общее количество вершин равно 8, так что это невозможно, поэтому это не является графическим.

Следовательно, только вариант I) и III) являются графической последовательностью, а ответ — вариант-D

Это решение предоставлено Nirmal Bharadwaj.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2010 | Вопрос 28

0.00 (0%) 0 votes