Loading AI tools
De Wikipedia, la enciclopedia libre
En teoría de grafos, un grafo bipartito completo es un grafo bipartito en el que todos los vértices de uno de los subconjuntos de la partición están conectados a todos los vértices del segundo subconjunto, y viceversa.[1]
Grafo bipartito completo | ||
---|---|---|
Un grafo bipartito completo con m = 5 y n = 3 | ||
Vértices | n + m | |
Aristas | mn | |
Radio | ||
Diámetro | ||
Cintura | ||
Automorfismos | ||
Número cromático | 2 | |
Índice cromático | max{m, n} | |
Este concepto se puede generalizar al de grafo s-bipartito completo, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.[1]
Un grafo bipartito completo es un grafo bipartito tal que Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.[1]
El grafo completo bipartito con particiones de tamaño y es denotado como .[1]
Sea un grafo bipartito con y , se verifica:[cita requerida]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.