Complete bipartite graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Complete bipartite graph''' --- полный двудольный граф. A bipartite graph <math>G = (X,Y,E)</math>, denoted <math>K_{m,n}</math>, in which …») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Complete bipartite graph''' | '''Complete bipartite graph''' — ''[[полный двудольный граф]].'' | ||
A bipartite graph <math>G = (X,Y,E)</math>, denoted <math>K_{m,n}</math>, in which every | A [[bipartite graph]] <math>\,G = (X,Y,E)</math>, denoted <math>\,K_{m,n}</math>, in which every | ||
vertex of <math>X</math> is adjacent to every vertex of <math>Y</math>. Here <math>m = | [[vertex]] of <math>\,X</math> is [[adjacent vertices|adjacent]] to every vertex of <math>\,Y</math>. Here <math>\,m = | ||
|X|</math> and <math>n = |Y|</math>. The ''treewidth'' of '''complete bipartite graph''' is <math>\min(m,n)</math>. | |X|</math> and <math>\,n = |Y|</math>. The ''[[treewidth of a graph|treewidth]]'' of '''complete bipartite graph''' is <math>\,\min(m,n)</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 10:48, 24 октября 2018
Complete bipartite graph — полный двудольный граф.
A bipartite graph [math]\displaystyle{ \,G = (X,Y,E) }[/math], denoted [math]\displaystyle{ \,K_{m,n} }[/math], in which every vertex of [math]\displaystyle{ \,X }[/math] is adjacent to every vertex of [math]\displaystyle{ \,Y }[/math]. Here [math]\displaystyle{ \,m = |X| }[/math] and [math]\displaystyle{ \,n = |Y| }[/math]. The treewidth of complete bipartite graph is [math]\displaystyle{ \,\min(m,n) }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.