Граф (неориентированный граф)

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф (неориентированный граф) (Graph (undirected graph)) — это


1. Пара (V,E), где V — непустое множество объектов некоторой природы, называемых вершинами графа, а E — подмножество двухэлементных подмножеств множества V, называемых ребрами графа. Множества вершин и ребер графа G обозначают V(G) и E(G) соответственно. Если |V(G)| = n и |E(G)| = m, то говорят о (n,m)-графе G.

2. Пара (V,E), где V — множество вершин графа, а E — множество ребер — есть подмножество множества V_{-}^{2} / \sim классов эквивалентности, на которые множество V_{-}^{2} = \{(v,w) | v
\neq w \} разбивается отношением эквивалентности: (v_{1},w_{1}) \sim (v_{2},w_{2}) \Leftrightarrow (v_{1},w_{1}) =
(v_{2},w_{2}) или (v_{1},w_{1}) = (w_{2},v_{2}).

Graph.png

3. Тройка (V,E,P), где V — множество вершин, E — множество объектов некоторой природы, отличной от природы вершин, называемых ребрами, Pинцидентор, сопоставляющий с каждым ребром e \in E пару граничных вершин v и w из V.

4. Общее название как для неориентированного, так и для ориентированного графов.

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.