Решения задач по теории графов

Теория графов

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 08 Сентябрь 2008; Просмотров: 14276

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

Рис. 1

Подробнее... Добавить комментарий

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 17 Апрель 2008; Просмотров: 9742

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

Подробнее... Добавить комментарий

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 17 Апрель 2008; Просмотров: 10200

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

Подробнее... Добавить комментарий

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 17 Апрель 2008; Просмотров: 4621

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

Подробнее... Добавить комментарий

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 17 Апрель 2008; Просмотров: 4459

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

Подробнее... Добавить комментарий

Подробности: Автор: Super User; Категория: Теория графов; Опубликовано: 17 Апрель 2008; Просмотров: 4881

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