Подробности

Автор: Super User

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

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

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

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

     
                       Рис. 1

Подробности

Автор: Super User

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

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

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

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

Подробности

Автор: Super User

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

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

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

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

Подробности

Автор: Super User

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

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

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

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

Подробности

Автор: Super User

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

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

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

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

Подробности

Автор: Super User

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

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

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

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

Подробности

Автор: Super User

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

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

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

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