Grafos

Solo disponible en BuenasTareas
  • Páginas : 2 (494 palabras )
  • Descarga(s) : 0
  • Publicado : 11 de febrero de 2010
Leer documento completo
Vista previa del texto
GRAFO COMPLETO:

En en el campo de la teoría de grafos, un grafo completo es aquél donde todas sus aristas conectan cada par de vértices. El grafo completo de n vértices tiene n vértices y n(n −1)/ 2aristas, y se nota Kn. Es un grafo regular con todos sus vértices de grado n − 1. Ningún grafo completo tiene Lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafocon una eliminación de vértices es aplicarla a todos.



K1

K2

K3

K4

K5

K6

K7

K8

GRAFOS DE CICLOS:En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un poligono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero queaparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lotanto cada vértice tiene dos aristas incidentes.Un grafo ciclo dirigido es una versión dirigida de un grafo ciclo, con todas las aristas orientadas hacia una misma dirección.
En un Grafo ciclodirigido, el grado de salida del vértice es 1 y el de entrada también es 1.

si G(V,A) es un ciclo Cn, el grafo tiene n vertices V={v1,v2......vn)  y n aristas formadas de la siguiente manera:GRAFOS DE RUEDA:

Obtenemos la rueda Wn cuando añadimos un vertice adicional al ciclo Cn para n˃3, y conectamos este nuevo vertice con cada uno de los n vertices de Cn mediante una nueva arista.
nGRAFOS DE N-CUBOS:

Un n-Cubo, denotado por Qn, es el grafo que tiene v´ertices que representan las 2n cadenas de bits de longitud n. dos v´ertices son adyacentes si y solo si las cadenas querepresentan difieren en solo un bit.

GRAFOS BIPARTITOS:

Un grafo bipartito es un grafo no dirigido G D .V; E/ cuyo conjunto de vértices V es unión de dos conjuntos disjuntos V1 y V2 de forma que...
tracking img