Complete bipartite graph

Материал из WEGA
Перейти к навигации Перейти к поиску

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.