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