Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. A) Естественно-правовая теория
  2. IV.6.2. Метод 1 (IP PMM Часть XIV, раздел 2, Приложение C)
  3. Quot;Трудовая" теория Ф. Энгельса
  4. VIII.1. ТЕОРИЯ
  5. А) Теория экономики предложения
  6. А. Оппозиция логичных и нелогичных действий как исходноеотношение социальной системы. Теория действия Парето и теория действия Вебера
  7. А.Бандура и теория социального обучения.
  8. Административная теория А. Файоля.
  9. Административная теория Л. Файоля
  10. Айсысы экономикалық теорияның пәні болып табылады?

Вариант № 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; просмотров: 83; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Упражнения. 10.1. Найти хроматические числа для графов: | Часть 1. 1.5. а) AÈB=[-5; 8]; AÇB=[0; 1]; A\B=(1; 8]; B\A=[-5; 0);
lektsii.com - Лекции.Ком - 2014-2018 год. (0.011 сек.) Главная страница Случайная страница Контакты