13:54
Постройте граф, соответствующий матрице инцидентности

Задана матрица инцидентности неориентированного графа G:

 

e1

e2

e3

e4

e5

v1

1

1

0

1

0

v2

1

0

0

0

1

v3

0

1

1

0

0

v4

0

0

1

1

1

Постройте граф, соответствующий данной матрице.

Решение.

 

ребра

вершины

 

e1

e2

e3

e4

e5

v1

1

1

0

1

0

v2

1

0

0

0

1

v3

0

1

1

0

0

v4

0

0

1

1

1

1) Строим четыре вершины: v1,v2,v3,v4

2) Вершины соединяем ребрами по правилу:

 

 

ребра

вершины

 

e1

e2

e3

e4

e5

v1

1

1

0

1

0

v2

1

0

0

0

1

v3

0

1

1

0

0

v4

0

0

1

1

1

 

Следовательно ребро e1 соединяет вершины v1 и v2,  и т.д.

Получаем


 

Категория: Теория графов | Просмотров: 4628 | Добавил: Admin | Рейтинг: 0.0/0
Всего комментариев: 0
avatar