:
Gutierrez Mendoza Karina
Definición de grafo:
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.’‘’
Tipos de grafos
Existen dos tipos de grafos los no dirigidos y los dirigidos.
• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).
• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.
Se dice que el grafo G = (V, E) es
a) Un grafo regular de grado n si todos sus vértices tienen grado n.
b) Un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices
c) Un ciclo si V = {v1, v2, . . . vn}, n³> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1)}. Se denota por Cn al ciclo de n vértices
d)Una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices
e)Un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.
f)Un grafo bipartido si V=V 1 UV 2? y cada arista de E une un vértice de V1 y otro de V2
g)Un grafo bipartido completo si V=V 1 UV 2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
Una pequeña presentacion
Presentacion en power point sobre tipos de grafos
Bibliografia’‘’
http://www.infovis.net/printMag.php?num=137&lang=1
http://docencia.udea.edu.co/regionalizacion/teoriaderedes/tiposu1.html
http://bochica.udea.edu.co/~rflorez/ed1/grafos/grafos01.html
Sitio WEB Recomendado
Estructura de Datos click here
prof lauro soto
