Diferencia entre revisiones de «Knm»
(→Definición.) |
|||
| Línea 6: | Línea 6: | ||
==Definición.== | ==Definición.== | ||
| − | Una definición formal de ''K<sub>n,m</sub>'' sería que siendo ''K<sub>n,m</sub>=<V<sub>1</sub> U V<sub>2</sub>,A>'', donde ''V<sub>1</sub>'' y ''V<sub>2</sub>'' son las dos particiones del conjunto de vértices | + | Una definición formal de ''K<sub>n,m</sub>'' sería que siendo ''K<sub>n,m</sub>=<V<sub>1</sub> U V<sub>2</sub>,A>'', donde ''V<sub>1</sub>'' y ''V<sub>2</sub>'' son las dos particiones del conjunto de vértices y ''A'' es la colección de aristas; si ''|V<sub>1</sub>|=n'',''|V<sub>2</sub>|=m'' y ''A=V<sub>1</sub>xV<sub>2</sub>'' entonces ''K<sub>n,m</sub>'' es un '''grafo bipartido completo de orden ''n'' y '''m'' '''. |
A diferencia de un grafo bipartido común el conjunto de aristas es subconjunto no nulo de ''V<sub>1</sub>xV<sub>2</sub>''. | A diferencia de un grafo bipartido común el conjunto de aristas es subconjunto no nulo de ''V<sub>1</sub>xV<sub>2</sub>''. | ||
Revisión del 00:24 26 nov 2011
| ||||||
Kn,m. Grafo bipartido completo cuyas particiones del conjunto de vértices cumplen que V1=n y V2=m respectivamente y que todos los vértices de V1 tienen aristas a todos los de V2.
Definición.
Una definición formal de Kn,m sería que siendo Kn,m=<V1 U V2,A>, donde V1 y V2 son las dos particiones del conjunto de vértices y A es la colección de aristas; si |V1|=n,|V2|=m y A=V1xV2 entonces Kn,m es un 'grafo bipartido completo de orden n y m .
A diferencia de un grafo bipartido común el conjunto de aristas es subconjunto no nulo de V1xV2.
Casos especiales.
Se sabe de un caso de grafo completo que es a su vez grafo bipartido completo: K2=K1,1.
También uno de los grafos de Kuratowski es un grafo bipartido completo: K3,3.
usado en la definición formal del matemático de origen polaco Kazimierz Kuratowski de grafo planar.
Fuentes.
- K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988.
- Grafo bipartito completo en Wikipedia
