analisis de conexidad

Actividad 3, Unidad 3

Análisis de conexidad

a. Determina la conexidad puntual de los siguientes grafos

Bien, para ello; denotemos que la conexidad puntual (o de vértices) k(G) de una gráficaconexa G (que no sea una gráfica completa) es el número mínimo de vértices cuya
eliminación desconecta G.
Por lo que para:
Grafo
G1
G2
G3
G4

Vértices en cuestión
bóc
cód
Se requierenmás de un vértice; a,c ó c,d
Se requieren más de un vértice; a y d, vértices no
adyacentes

b. Determina la conexidad lineal de los siguientes grafos

Conexidad puntual k(G)
1
1
2
2

Primeromencionamos que la conexidad lineal (o de aristas) λ(G) de una gráfica conexa
G es el número mínimo de aristas que cuando son removidas desconectan G.
Entonces, efectuando análisis, tenemos:
GrafoG1
G2
G3
G4

Aristas en cuestión
bc ó bd
cd
Se requieren más de una arista; ac y bc
Se requieren más de una arista; ab, ad, y cd

Conexidad lineal λ(G)
1
1
2
3

c. De acuerdo alteorema de Menger para la conexidad puntual, determina
el siguiente grafo

y

,

,

para

Bien, exponiendo el teorema respectivo, que establece que para cada par de vértices no
adyacentesestas dos medidas son iguales. Una formulación equivalente del teorema
establece que si V y W son conjuntos de vértices no vacíos en una gráfica, entonces el
número máximo de trayectorias internamentedisjuntas V-W es igual al número mínimo
de vértices cuya eliminación destruye todas esas trayectorias. Estamos hablando de la
conexidad puntual.
Se observa que en k(v,w) como en µ(v,w) son 3trayectorias que no tienen vértices
en común, es decir; son trayectorias internamente disjuntas.

a. De acuerdo al teorema de Menger para la conexidad lineal, determina
siguiente grafo

,

y

,para el

Desplegando el teorema respectivo, el cual refiere, que dados “v y w”, dos vértices en
una gráfica G. Un conjunto S de aristas es un conjunto de aristas de corte v-w, si v y w
están...