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 /
AQUI EMPIEZA EL TRABAJO ESPECIAL REALIZADO POR GARCIA VASQUEZ MISAEL,
5.2 TIPOS DE GRAFOS
Grafo
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad
Grafos simples [editar]
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina GRAFO COMPLEJO.. 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, Grafos conexos [editar]
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en “componentes (fuertemente) conexas”, es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.
VIDEO DE TIPOS DE GRAFOS EN REPRESENTACION GRAFICA
http://es.youtube.com/watch?v=O8XEOz8FCDQ
AQUI EMPIEZA EL TRABAJO DE ORTEGA ROMERO CHRISTIAN DEL 1B DE INFROMATICA
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = (1, 2), (1, 3), (2, 4), (2, 5), (3, 6) G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> } Algunos de los principales tipos de grafos son los que se muestran a continuación:
• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota .
• Un grafo bipartito regular: se denota donde m, n es el grado de cada conjunto disjunto de vértices.
• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.