Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Вариант № 1.

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

 

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

 

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

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. Найти количество вершин и ребер в графе Е4.

Вариант № 2.

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

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

А=

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

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. Найти хроматическое число графа К6.

Вариант № 3.

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

 

 

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

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

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. Используя алгоритм фронта волны, найти минимальный путь из вершины v1 в вершину v5 в орграфе, заданном матрицей смежности

 

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. Используя алгоритм Форда-Беллмана, найти минимальный путь из вершины v1 в вершину v5 в нагруженном орграфе, заданном матрицей длин дуг:

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. Используя алгоритм фронта волны, найти минимальный путь из вершины v1 в вершину v5 в орграфе, заданном матрицей смежности

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. Доказать, что граф Е3 является двудольным.


Ответы


Поделиться:

Дата добавления: 2015-01-29; просмотров: 282; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты