En teoria de grafos, un grafo bipartit complet és un grafo bipartit en el que tots els vèrtiços d'un dels subconjunts de la partició estan conectats a tots els vèrtiços del segon subconjunt, i viceversa.[1]

Grafo bipartit complet

Este concepte es pot generalisar al de grafo s-bipartito complet, com un grafo el conjunt del qual de vèrtiços es pot particionar en s subconjunts, de modo que tots els parells de vèrtiços pertanyents a subconjunts diferents són adjacents.[1]

Definició

Un grafo bipartit complet G:=(V1∪V2,E) és un grafo bipartit tal que ∀v1∈V1,∀ v2∈V2⇒e(v1,v2)∈E. És dir, un grafo bipartit complet està format per dos conjunts disjunts de vèrtiços i totes les possibles arestes que unixen eixos vèrtiços.[1]

El grafo complet bipartito en particions de tamany |V1|=m i |V2|=n, és denotat com Km,n.[1]

Eixemples

Vore també

Referències

  1. ↑ 1,0 1,1 1,2 1,3 Wasserman y Faust, 2013, «Grafos i matrius» (per Dawn Iacobucci), pp. 121-188.

Bibliografia

  • Wasserman, Stanley; Faust, Katherine (2013). Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.