Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 08 Сентябрь 2008

Просмотров: 13855

Для графа G=(Y,V) (рис.1) построить матрицы смежностей и инциденций, и по матрице смежностей – матрицу достижимостей, выделить связные (сильные) компоненты, и построить конденсацию графа. Найти число путей длиной 3 из Y₆ в Y₂
     

     
                       Рис. 1

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 9460

На заданной сети (Рис. 1) найти максимальный поток из X4 в X1 и минимальный разрез.

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 9798

В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 4379

В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все минимальные доминирующие множества (МДМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 4139

В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все максимальные независимые множества (МНМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 4689

Дан исходный граф G = (X, V) (рис. 1). Построить порождённый подграф G' = (X', V'), который получается из исходного после удаления указанных вершин и инцидентных им ребер. Найти в G' кратчайший остов.
Вершина, которую необходимо удалить - Х8, Х9

Подробности

Автор: Super User

Категория: Теория графов

Опубликовано: 17 Апрель 2008

Просмотров: 6098

Найти все пути из Х4 в Х7 в графе G=(Х,Г) изображенном на рисунке 1.