Навигация
Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф
6512
знаков
11
таблиц
15
изображений
5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
Остовные подграфы
G’1(X1,A1)
G’2(X2,A2)
Произвольные подграфы
G1’’ (X1’’,A1’’)
|
G2’’ (X2’’,A2’’) Порожденные подграфы
|
G1P(X1P,A1P) G2P(X2P,A2P)
6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
Локальные степени графа G1
1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ;
1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ;
1 (х3)=2 ; 2 (х3)=2 ; (х3)=4 ;
1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ;
1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ;
1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ;
1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ;
Локальные степени графа G2
1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ;
1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ;
1 (х3)=3 ; 2 (х3)=2 ; (х3)=4 ;
1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ;
1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ;
1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ;
1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ;
Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.
Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.
7. Определить хроматические и цикломатические числа данных графов.
Хроматическое число γ для графа G1 = 4
Хроматическое число γ для графа G2 = 4
Цикломатические числа графов
V(G1)=m-n+r, где m - число рёбер (дуг);
n – число вершин;
r – число компонент связности.
V(G1)=14-7+1=8;
V(G2)=14-7+1=8;
8. Найти все базы графа.
Базы графа G1
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}
Базы графа G2
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}
9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.
Сильные компоненты связности G1
СК={x1, x2, x3, x4, x5, x6, x7}
Сильные компоненты связности G2
СК={x1, x2, x3, x4, x5, x6, x7}
Конденсация графа G1 Конденсация графа G2
Похожие работы
... можно строить схемы замещения реальных элементов цепи. 3. Топологические элементы схем Кроме рассмотренных элементов существуют топологические элементы, которые позволяют описать структуру цепи. Основные понятия: 1) Ветвь – соответствует участку цепи, в котором все элементы стоят последовательно, т.е. по которому протекает один и тот же ток. 2) Узел – место соединения трех и более ветвей ...
... В СМО без отказов заявка либо сразуназначается на обслуживание, если в момент ее поступлениясвободен хотя бы один канал обслуживания, либо безусловнопринимается в очередь на обслуживание. Потоки событий. Типы потоков Переход системы в некоторое состояние Si называетсясобытием. В процессе работы система неоднократно можетвозвращаться в состояние Si. Последовательность ...
... некая иерархическая структура. Третья идея ССА широкое использование графических нотаций, что облегчает понимание сложных систем. В результате можно дать следующее определение ССА: структурным системным анализом называется метод исследования, проектирования и описания сложных систем в виде иерархии "черных ящиков" с помощью графических средств. Другие принципы ССА Методология ССА строится ...
... ; система — это единое и неразрывное целое, являющееся целостной системой для нижестоящих иерархических уровней, имеются фиксированные связи системы с внешней средой. Рассмотрим основные понятия, характеризующие строение и функционирование систем. Под элементом принято понимать простейшую неделимую часть системы. Ответ на вопрос, что является такой частью, может быть неоднозначным и зависит от ...
0 комментариев