Аноним

Граф (неориентированный граф): различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 3: Строка 3:


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


'''2.''' Пара <math>(V,E)</math>, где <math>V</math> ---
'''2.''' Пара <math>(V,E)</math>, где <math>V</math> ---
множество ''вершин'' графа, а <math>E</math> --- множество ''ребер'' ---
множество [[Вершина|''вершин'']] графа, а <math>E</math> --- множество [[Ребро|''ребер'']] ---
есть подмножество множества <math>V_{-}^{2} / \sim</math> классов
есть подмножество множества <math>V_{-}^{2} / \sim</math> классов
эквивалентности, на которые множество <math>V_{-}^{2} = \{(v,w) | v
эквивалентности, на которые множество <math>V_{-}^{2} = \{(v,w) | v
Строка 17: Строка 17:
(v_{2},w_{2})</math> или <math>(v_{1},w_{1}) = (w_{2},v_{2}).</math>
(v_{2},w_{2})</math> или <math>(v_{1},w_{1}) = (w_{2},v_{2}).</math>


'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> --- множество ''вершин'', <math>E</math>
'''3.''' Тройка <math>(V,E,P)</math>, где <math>V</math> --- множество [[Вершина|''вершин'']], <math>E</math>
--- множество объектов некоторой природы, отличной от природы
--- множество объектов некоторой природы, отличной от природы
вершин, называемых ''ребрами'', <math>P</math> --- ''инцидентор'',
вершин, называемых [[Ребро|''ребрами'']], <math>P</math> --- ''инцидентор'',
сопоставляющий с каждым ребром <math>e \in E</math> пару ''граничных вершин''
сопоставляющий с каждым ребром <math>e \in E</math> пару ''граничных вершин''
<math>v</math> и <math>w</math> из <math>V</math>.  
<math>v</math> и <math>w</math> из <math>V</math>.  


'''4.''' Общее название как для
'''4.''' Общее название как для
неориентированного, так  и  для  ориентированного графов.
[[Неориентированный граф|неориентированного]], так  и  для  [[Ориентированный граф|ориентированного графов]].


== См. также ==
== См. также ==