Двудольные графы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «=== Двудольные графы ===»)
 
(Двудольные графы)
Строка 1: Строка 1:
 
=== Двудольные графы ===
 
=== Двудольные графы ===
 +
{{Определение
 +
|definition=
 +
<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
 +
}}

Версия 21:28, 22 ноября 2016

Двудольные графы

Определение:
Двудольный граф или биграф (англ. bipartite graph) — граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с [math]n[/math] вершинами в одной доле и [math]m[/math] во второй обозначается [math]K_{n,m}[/math].