Двудольные графы — различия между версиями
(→Двудольные графы) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | <span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>. | + | <span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} [[Основные определения теории графов|граф]], множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>. |
}} | }} | ||
[[Файл: Bipartite_graph.png|300px|thumb|center|Пример двудольного графа]] | [[Файл: Bipartite_graph.png|300px|thumb|center|Пример двудольного графа]] | ||
| − | [[Категория: | + | [[Категория: Алгоритмы и структуры данных]] |
| + | [[Категория: Основные определения теории графов]] | ||
Текущая версия на 19:31, 4 сентября 2022
| Определение: |
| Двудольный граф или биграф (англ. bipartite graph) — граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с вершинами в одной доле и во второй обозначается . |
