Grafos.
Nociones básicas
Introducción
I Definiciones y ejemplos I Tipos
de grafos I Representación
de grafos I Representación
de grafos en el ordenador I Conectividad
1.6. Conectividad. Componentes conexas. Vértice y aristas de corte
1.6.
Conectividad. Componentes conexas. Vértice y aristas de corte.
Definición
1.6.1. Sea G=(V, E) un grafo. Se dice que entre
los vértices v0
y vk
existe un recorrido de longitud
k si existe una sucesión de vértices
y aristas de la forma (v0, v1), (v1, v2
), (v2, v3) ...(vk-1,vk). Si v0=vk
se dice que el recorrido es cerrado.
Ejemplo 1.6.2
Definición 1.6.3. Sea G=(V,
E) un grafo y u,
v e V. Se denomina camino de longitud k
entre los vértices u
y v a un recorrido de longitud k desde el vértice u al vértice v que tiene k aristas diferentes entre si. Si
un camino tiene todos sus vértices diferentes se denomina camino simple. Un ciclo
es un camino de u
a u. Un ciclo simple es un ciclo donde los vértices no se repiten.
Ejemplo 1.6.3. Dar ejemplo de camino, camino simple, ciclo y
ciclo simple en el grafo del ejemplo anterior
Proposición 1.6.4. Si A
es la matriz de adyacencia de un grafo simple G entonces el elemento ij-esimo dela matriz An es el número de recorridos de longitud n desde el vértice vi al vértice vj.
Proposición 1.6.5. Un grafo G=(V, E) bipartido no tiene ciclos de longitud impar.
Proposición 1.6.6. Si G tiene sólo dos vértices impares existe un camino entre ellos.
Definición. 1.6.7. Un grafo G=(V, E) se denomina conexo
si existe un camino entre cualquier par de vértices distintos de G.
Definición 1.6.8. Sea G=(V, E) un grafo no
conexo. Se denomina componente
conexo de G
a un subgrafo conexo maximal de G.
Ejemplo 1.6.9.
Proposición 1.6.10. Sea G=(V,
E) un grafo. Los componentes conexos de G forman una partición en G.
Definición 1.6.11. Un vértice v se denomina vértice corte
(o punto de articulación) de
G si el grafo G-{v} tiene más componentes conexos
que el grafo G.
Una arista e se
denomina puente si G-{e} tiene más componentes conexas que G. Los bloques de un grafo G
son los subgrafos maximales de G
que no tienen vértices corte.
Proposición 1.6.12. Una arista e de un grafo conexo es un puente de G si y solo si la arista e no pertenece a ningún ciclo de G.
Proposición 1.6.13. Si dos bloques comparten un vértice, éste debe ser un vértice-corte
Ejemplo 1.6.14. Hallar
un vértice corte, un puente y un bloque del grafo del ejemplo 1.6.9.
Definición 1.6.15. Un recorrido dirigido en un digrafo es una sucesión de vértices y arcos de la forma v0e1v1e2...vk-1 ekvk , donde el arco ei tiene como extremos inicial y final vi-1 y vi , respectivamente. Si no se repiten ni vértices ni aristas se denomina camino dirigido. Dicho camino se llama camino de v0 a vk y su longitud es k.
Definición 1.6.16. Un digrafo D=(V, E) es fuertemente conexo si para todo par de vértices u y v existe un camino dirigido que va de u a v.
Ejemplo 1.6.17. Dígrafo fuertemente conexo
Definición 1.6.18. Dado un digrafo D, podemos considerar el grafo G no dirigido que se obtiene al sustituir cada arco uv por la arista (u,v). Si este grafo es conexo, diremos que el digrafo D es débilmente conexo.
Ejemplo 1.6.19. Digrafo débilmente conexo que no es fuertemente conexo
Definición 1.6.20. Sea G un grafo no dirigido. Si al asignar un sentido a cada arista de G (orientación de G) se obtiene un digrafo fuertemente conexo, entonces se dice que G es un grafo orientable.
Ejemplo 1.6.21. Grafo simple orientable.
