Часть 2. Теория графов

Вариант № 1.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Дан граф G. Задать длины ребер данного графа. Составить матрицу длин ребер. Найти взвешенные эксцентриситет, радиус и центр.

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности:

4. Дан граф G=(V,X). V={1,2,3,4,5}, X={(1,2), (1,3), (2,3), (2,4), (2,5), (3,4),( 3,5), (5,1)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти количество вершин и ребер в графе Е⁴.

Вариант № 2.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти по формуле матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V, X). V={1, 2, 3, 4, 5}. X={(1, 3), (2, 4), (2, 5), (3, 2), (3, 4), (3, 5), (4, 1), (4, 5)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти хроматическое число графа К₆.

Вариант № 3.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Найти по формуле матрицу связности графа G, заданного матрицей смежности:

3. Используя алгоритм Форда-Беллмана, найти минимальный путь из вершины v₁ в вершину v₅ в нагруженном орграфе, заданном матрицей длин дуг:

4. Дан граф G=(V,X). V={1,2,3,4,5}, X={(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4),( 3,5), (4,5)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Существует ли полный граф с четырнадцатью ребрами? Ответ пояснить.

Вариант № 4.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V,X). V={1,2,3,4,5}. X={(1,2), (1,3), (1,4), (3,4), (3,5), (4,2), (4,5), (5,2)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти хроматическое число графа К_3,4.

Вариант № 5.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Найти по формуле матрицу связности графа G, заданного матрицей смежности:

3. Используя алгоритм Форда-Беллмана, найти минимальный путь из вершины v₁ в вершину v₅ в нагруженном орграфе, заданном матрицей длин дуг:

4. Дан граф G=(V,X). V={1,2,3,4,5}, X={(1,3), (1,4), (2,4), (2,5), (3,4), (3,5), (4,5), ( 5,1)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти количество полных трехвершинных подграфов графа К_5,6.

Вариант № 6.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти по формуле матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V,X). V={1,2,3,4,5}. X={(1,4), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5), (5,1)}. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Доказать, что граф Е³ является двудольным.

Ответы