Лекция 18. Понятие графа. Способы задания графа. Методика выделения компонента связности в графе
Графом G(V, E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер). G(V, E): Число вершин графа G обозначим р, а число ребер – q. р(G) = |V| q(G) = |E|. Часто рассматриваются следующие родственные графам объекты. 1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества 2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). 3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом. Далее выражение: граф G(V, E) означает неориентированный граф без петель и кратных ребер. Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.
|
, E 
VxV.
- дугами (G(V, 
