1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|id = finite_graph
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
{{Определение
|id = isomorphic_graphs
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа <tex>A</tex> и <tex>B</tex> называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.
}}
{{Определение
|id=def_edge_und
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
{{Определение
|id = isolated_vertex
|definition =
'''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex>
}}
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
== Часто используемые графы ==
{{Определение
|id = defFullGraph
|definition=
'''Полный граф''' (англ. ''complete graph'', ''clique'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
{{Определение
|id = defBiparateGraph
|definition=
<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
{{Определение
|id = defRegularGraph
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
{{main|Дерево, эквивалентные определения}}
{{Определение
|id=defTree
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}
