Diferencia entre revisiones de «Grafo conexo»

Contenido eliminado Contenido añadido
Sin resumen de edición
Sin resumen de edición
Línea 1:
[[Archivo:Halin_graph.svg|thumb|Grafo conexo.]]
 
[[Archivo:Chromatically_equivalent_graphs.svg|thumb|Grafo no conexo]]
En [[teoría de grafos]], un '''grafo conexo''' es un [[grafo]] en que todos sus [[vértice (teoría de grafos)|vértices]] están conectados a través de un [[camino (teoría de grafos)|camino]] (en el caso de que el grafo sea [[grafo no dirigido|no dirigido]])<ref name=CC17>{{cita publicación |autor1=Carrasco Pacheco, José Luis |autor2=Contreras Ordaz, Marco Antonio |título=Modelado dinámico por inspección para convertidores de potencia CD a CD commutados: Un enfoque basado en grafos |editorial=Universidad Tecnológica de la Mixteca |url=http://repositorio.utm.mx:8080/jspui/handle/123456789/175 |año=2017 |fechaacceso=25 de abril de 2021}}</ref> o bien a través de una sucesión de [[arista (teoría de grafos)|aristas]], sin importar el sentido de estas (en el caso de que el grafo sea [[grafo dirigido|dirigido]]).
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.
 
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 91 ⟶ 92:
== Véase también ==
* [[Camino (teoría de grafos)]]
 
== Referencias ==
{{listaref}}
 
{{Control de autoridades}}