Diferencia entre revisiones de «Grafo conexo»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 2:
{{en uso|MialiasenlaWikipediaenespañol|t=20190601105550}}
[[Archivo:Chromatically_equivalent_graphs.svg|thumb|Grafo no conexo]]
En [[teoría de grafos]], un [[grafo]] <math>G</math> se dice '''conexo''' si, para cualquier par de [[Vértice (teoría de grafos)|vértices]] ''u'' y ''v'' en ''G'', existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de ''u'' a ''v''. 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 doblemente 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 con base en é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.
== Conceptos relacionados ==
Línea 56 ⟶ 58:
</source>
== Conexidad en grafos ==
En los grafos dirigidos existen 3 tipos de niveles de conexidad por los que se llaman a los grafos como:
* '''Conexos''': Idéntico a la definición antes vista.
* '''Débilmente conexos''': Dígrafos que no son conexos pero que sus equivalentes no orientados o sosías sí lo son.
* '''Fuertemente conexos''': Grafos orientados que entre cualquier par de nodos distintos existe un arco que los une.
Los grafos fuertemente conexos nunca son simples pues exige que siempre entre un par de vértices habrá un par de aristas (una de ida y otra de vuelta).
== Tipos ==
'''Grafo dirigido'''
Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.
Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w). Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.
'''Grafo no dirigido'''
Un grafo no dirigido ( consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado.
por ejemplo:
si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.
'''Grafo dirigido con peso'''
Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.
== Representación de grafos ==
De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.
Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.
[[Categoría:Familias de grafos|Conexo]]
| |||