Главное меню

Вход на сайт

Кто на сайте?

Сейчас 176 гостей и ни одного зарегистрированного пользователя на сайте

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

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

Для графа G=(Y,V) (рис.1) построить матрицы смежностей и инциденций, и по матрице смежностей – матрицу достижимостей, выделить связные (сильные) компоненты, и построить конденсацию графа. Найти число путей длиной 3 из Y6 в Y2
     
Image
     
                       Рис. 1
На заданной сети (Рис. 1) найти максимальный поток из X4 в X1 и минимальный разрез.
Image
В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1
Image
В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все минимальные доминирующие множества (МДМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)
Image
В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все максимальные независимые множества (МНМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)
Image
Дан исходный граф G = (X, V) (рис. 1). Построить порождённый подграф G' = (X', V'), который получается из исходного после удаления указанных вершин и инцидентных им ребер. Найти в G' кратчайший остов.
Вершина, которую необходимо удалить - Х8, Х9

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