Diferencia entre revisiones de «Grafo conexo»
Contenido eliminado Contenido añadido
m Añadiendo la Categoría:Conectividad de grafos mediante HotCat |
Sin resumen de edición |
||
Línea 2:
[[Archivo:Chromatically_equivalent_graphs.svg|thumb|Grafo no conexo]]
En [[teoría de grafos]], un [[grafo]] <math>G</math> no dirigido 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) de ''u'' a ''v''. Un grafo es conexo si cada par de vértices está conectado por un [[camino (teoría de grafos)|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 estos 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.
Línea 88:
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.
== Véase también ==
* [[Camino (teoría de grafos)]]
{{Control de autoridades}}
[[Categoría:Familias de grafos|Conexo]]
| |||