Информационные технологии проектирования электронных средств

- 16 - ЛЕКЦИЯ 5. Основные понятия теории графов Граф G ( Х , Е ) задается множеством вершин x i ∈ X )1 ( ,n i = и множеством ребер или дуг e j ∈ Е ) 1 ( ,m j = , соединяющих между собой все или несколько вершин. Если x 1 и х 2 – концевые вершины дуги е j , то говорят, что вершины х 1 и х 2 инцидентны дуге е j . Две вершины x j и x k , соединенные дугой или ребром, называются смежными. Граф может быть ориентированным (рис. 3, а ) и неориентированным (рис. 3, б ). Ориентированный граф имеет ориентацию дуг, которая задается стрелкой. Другое употребляемое описание ориентированного графа G ( X , E ) со- стоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. х 2 х 2 х 1 х 2 х 3 х 4 х 5 е 2 е 1 х 3 х 3 х 1 е 9 е 3 х 1 е 6 е 8 х 6 е 7 х 4 х 6 х 4 е 5 е 4 х 5 х 5 х 6 х 7 х 8 х 9 х 10 х 11 а ) б ) Рис. 3 Рис. 4 Маршрут − последовательность дуг, в которой не учитывается их ориен- тация. Путем (ориентированным маршрутом) ориентированного графа G ( X,E ) называется последовательность дуг, в которой конечная вершина каждой дуги (отличной от последней), является начальной вершиной следующей дуги.