Los grafos
Páginas: 3 (686 palabras)
Publicado: 28 de junio de 2011
sábado 25 de junio de 2011APLICACION DE MATEMATICAS DISACRETAS_203
EMPLEO DE LOS GRAFOS
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de lasgráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas(edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
TIPOS DE FRAFOS
Completos:Es un grafo de n vértices que contiene una arista entre cada par de vértices distintos. Se denota como Kn.
Ciclos: Son grafos con n vértices (para n>= 3) y con un conjunto de aristas definido dela siguiente forma: { (v1,v2),(v2,v3),(v3,v4)�. (vn-1, vn), (vn, v1) }. Se denota como Cn.
Rueda: Obtenemos una rueda cuando añadimos un vértice al ciclo Cn y conectamos este nuevo vértice con cadauno de los vértices de Cn mediante nuevas aristas .
n-Cubos: En un grafo n-Cubo se definen vértices que representan 2n cadenas de bits de longitud n. Se debe tener en cuenta que dos vérticesserán adyacentes si las cadenas de bits que representan difieren exactamente en un bit.
Bipartitos: Se dice que un Grafo Simple G es bipartito si su conjunto de vértices V se puede dividir en dosconjuntos disjuntos V1 y V2 tales que cada arista del grafo conecta un vértice de V1 con un vértice de V2 (de manera que no haya ninguna arista que conecte entre sí dos vértices de V1 ni tampoco dosvértices de V2).
Bipartito Completo: El Grafo Bipartito Completo K m,n es el grafo cuyo conjunto de vértices está formado por dos subconjuntos con m y n vértices, respectivamente, y ahí una arista entredos vértices si, y sólo si, un vértice está en el primer subconjunto y el otro vértice está en el segundo subconjunto.
Caminos
Sean x, y " V, se dice que hay un camino en G de x a y si existe...
EMPLEO DE LOS GRAFOS
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de lasgráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas(edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
TIPOS DE FRAFOS
Completos:Es un grafo de n vértices que contiene una arista entre cada par de vértices distintos. Se denota como Kn.
Ciclos: Son grafos con n vértices (para n>= 3) y con un conjunto de aristas definido dela siguiente forma: { (v1,v2),(v2,v3),(v3,v4)�. (vn-1, vn), (vn, v1) }. Se denota como Cn.
Rueda: Obtenemos una rueda cuando añadimos un vértice al ciclo Cn y conectamos este nuevo vértice con cadauno de los vértices de Cn mediante nuevas aristas .
n-Cubos: En un grafo n-Cubo se definen vértices que representan 2n cadenas de bits de longitud n. Se debe tener en cuenta que dos vérticesserán adyacentes si las cadenas de bits que representan difieren exactamente en un bit.
Bipartitos: Se dice que un Grafo Simple G es bipartito si su conjunto de vértices V se puede dividir en dosconjuntos disjuntos V1 y V2 tales que cada arista del grafo conecta un vértice de V1 con un vértice de V2 (de manera que no haya ninguna arista que conecte entre sí dos vértices de V1 ni tampoco dosvértices de V2).
Bipartito Completo: El Grafo Bipartito Completo K m,n es el grafo cuyo conjunto de vértices está formado por dos subconjuntos con m y n vértices, respectivamente, y ahí una arista entredos vértices si, y sólo si, un vértice está en el primer subconjunto y el otro vértice está en el segundo subconjunto.
Caminos
Sean x, y " V, se dice que hay un camino en G de x a y si existe...
Leer documento completo
Regístrate para leer el documento completo.