Cortes Y Conectividad

´ Indice

Cortes y Conectividad
Jos´ Nicol´s Pi˜a Le´n e a n o
Departamento de Ingenier´ Matem´tica ıa a Universidad de Concepci´n o

13 de Noviembre del 2008

Jos´ N. Pi˜a L. e n

Cortes y Conectividad

´ Indice

´ Indice
1 2

Introducci´n o Definiciones B´sicas a Conectividad Arista-Conectividad Teorema de Menger arista-local Definiciones Teorema de Menger arista-local Teoremade Menger local Definiciones Teorema de Menger local Corolario Teoremas de Mengers
Jos´ N. Pi˜a L. e n Cortes y Conectividad

3

4

5

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ ıa

Indice
1 2

Introducci´n o Definiciones B´sicas a Conectividad Arista-Conectividad Teorema de Menger arista-localDefiniciones Teorema de Menger arista-local Teorema de Menger local Definiciones Teorema de Menger local Corolario Teoremas de Mengers
Jos´ N. Pi˜a L. e n Cortes y Conectividad

3

4

5

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ ıa

Cortes y Conectividad La conectividad de un grafo se basa en cuandif´ resulta ıcil cortar un grafo considerando sus vertices y sus aristas. Los resultados siguientes nos entregan una relaci´n entre que tan o conecta es un grafo, respecto de sus aristas y sus vertices, y cada par de vertices del grafo, respecto de sus caminos.

Jos´ N. Pi˜a L. e n

Cortes y Conectividad

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Mengerlocal Corolario Teoremas de Mengers Bibliograf´ ıa

Conectividad Arista-Conectividad

Indice
1 2

Introducci´n o Definiciones B´sicas a Conectividad Arista-Conectividad Teorema de Menger arista-local Definiciones Teorema de Menger arista-local Teorema de Menger local Definiciones Teorema de Menger local Corolario Teoremas de Mengers
Jos´ N. Pi˜a L. e n Cortes y Conectividad

3

4

5Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ ıa

Conectividad Arista-Conectividad

Conectividad
Definici´n Conectividad o La conectividad de un grafo G = (V , E ), es el m´ ınimo n´mero de u elementos de un conjunto S ⊂ V (G ) tal que G − S es no conexo denotado como κ(G ). Diremos que G es k-conexo siκ(G ) ≥ k.

Ejemplo conectividad Sea G : b a e
Jos´ N. Pi˜a L. e n Cortes y Conectividad

As´ κ(G ) = 2 ı c d e c d

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ ıa

Conectividad Arista-Conectividad

Conectividad
Definici´n Conectividad o La conectividad de un grafo G = (V , E ), es el m´ ınimon´mero de u elementos de un conjunto S ⊂ V (G ) tal que G − S es no conexo denotado como κ(G ). Diremos que G es k-conexo si κ(G ) ≥ k.

Ejemplo k-conexo Sea G : c b a e d

G es 1-conexo: c b d e
Jos´ N. Pi˜a L. e n Cortes y Conectividad

G es 2-conexo: c d e

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ıa

Conectividad Arista-Conectividad

Arista-Conectividad
Definici´n Arista-Conectividad o La arista-conectividad de un grafo G = (V , E ), es el m´ ınimo n´mero de elementos de un conjunto F ⊂ E (G ) tal que G − F es u no conexo denotado como λ(G ). Diremos que G es k-arista-conexo si λ(G ) ≥ k.

Ejemplo arista-conectividad Sea G : b a c d
Jos´ N. Pi˜a L. e n

As´ λ(G ) = 2 ı b a
Cortes yConectividad

c d

Introducci´n o Definiciones B´sicas a Teorema de Menger arista-local Teorema de Menger local Corolario Teoremas de Mengers Bibliograf´ ıa

Conectividad Arista-Conectividad

Arista-Conectividad
Definici´n Arista-Conectividad o La arista-conectividad de un grafo G = (V , E ), es el m´ ınimo n´mero de elementos de un conjunto F ⊂ E (G ) tal que G − F es u no conexo...