Grafos Definiciones

Cap´ıtulo 1 Grafos 1.1.

Definiciones B´ asicas y Ejemplos

Definici´ on 1.1.1. Un grafo simple G es un par (V, E) donde V es un conjunto finito cuyos elementos se denominan v´ertices. Llamaremos orden de G al n´ umero de v´ertices y lo denotaremos por |V |. E es un subconjunto finito de V × V , tal que si (a, b) ∈ E, entonces a 6= b y (b, a) ∈ E. Los elementos de E se denominan aristas. Si (a, b) ∈ E, debido a que (a, b) ∈ E ⇐⇒ (b, a) ∈ E, denotamos la arista que conecta a y b como {a, b}. Se dice que los v´ertices a y b son adyacentes cuando est´an conectados por una arista y los v´ertices a y b se denominan extremos de la arista. Gr´aficamente representaremos los v´ertices por puntos y las aristas por l´ıneas que los unen. En los grafos simples, dos v´ertices, si son adyacentes, est´an unidos por una u ´nica arista Ejemplo: El siguiente gr´afico representa un grafo con tres v´ertices y tres aristas:

Nosotros hemos dado la definici´on de un grafo simple, pero tambi´en existen otro tipo de grafos como:

3

CAP´ITULO 1. GRAFOS

4

Multigrafo Grafo en donde dos v´ertices distintos pueden estar unidos por m´as de una arista. Dos o m´as aristas que unen el mismo par de v´ertices distintos se denominan multiaristas. Pseudografo Una arista puede conectar un mismo v´ertice. Una arista que conecta un mismo v´ertice se denomina lazo. Digrafo Un grafo en el cual las aristas son pares ordenados. Es decir, (a, b) 6= (b, a). Gr´aficamente, la arista (a, b) se representa con una flecha dirigida de a a b. Ejemplo: El grafo de la derecha es un multigrafo, y el de la izquierda es un pseudografo.

lazo

Multiarista

Otra Cuadro 1.1: Grafos no simples

x

y

A lo largo de este curso nos centraremos en los grafos simples, por lo tanto, la palabra grafo implicar´a grafo simple si no se indica lo contrario. Definici´ on 1.1.2. Llamaremos grado de un v´ertice al n´ umero de aristas de las que es extremo. Se dice que un v´ertice es ’par’ o ’impar’ seg´ un lo sea su grado. Ejemplo: En este grafo, el v´ertice 5 tiene grado cuatro, y los dem´as grado uno.

Dado un conjunto, podr´ıamos hablar de subconjuntos; dado un ret´ıculo, podr´ıamos hablar de ret´ıculos, y dado un grafo, tambi´en podremos hablar de subgrafos. Definici´ on 1.1.3. Sea G = (V, E) un grafo. Un subgrafo de G es otro grafo G0 = (V 0 , E 0 ), tal que V 0 ⊆ V , E 0 ⊆ E y si {a, b} ∈ E 0 , entonces a, b ∈ V 0 . A la hora de representar un grafo simple, existen m´as herramientas que su gr´afico, como la matriz de adyacencia

´ 1.1. DEFINICIONES BASICAS Y EJEMPLOS

5

5

4

2

3

1

Cuadro 1.2: Definici´ on 1.1.4. Sea G un grafo de orden n. La matriz de adyacencia de G es una la matriz con n filas y n columnas, denotada A = (aij ), donde aij = 1 si los v´ertices i y j son adyacentes y aij = 0 en otro caso. La matriz de adyacencia de un grafo simple siempre es sim´etrica, es decir, aij = aji , y su diagonal es nula. Ejemplo: La matriz de adyacencia del grado de la figura 1.2 es: v1 v2 v3 v4 v5

1.1.1.

 v1 0  0   0   0 1

v2 0 0 0 0 1

v3 0 0 0 0 1

v4 0 0 0 0 1

v5 1 1 1 1 0

     

Caminos y conexidad

Supongamos que tenemos un grafo G y dos de sus v´ertices x, y. Una de las preguntas que se pueden plantear es si a trav´es de las aristas del grafo, se puede ir desde el v´ertice x al v´ertice y, es decir, si hay un camino que conecta x con y. Otra

x

y

CAP´ITULO 1. GRAFOS

6

Definici´ on 1.1.5. Sean x, y ∈ V , se dice que hay un camino en G de x a y si existe una sucesi´on finita no vac´ıa de aristas {x, v1 }, {v1 , v2 }, ..., {vn , y}. Si hay camino de x a y, entonces los v´ertices x a y se llaman los extremos del camino, el n´ umero de aristas del camino se denomina la longitud del camino, si los v´ertices no se repiten el camino se dice propio o simple, llamaremos sendero a un camino que nunca pasa dos veces por la misma arista, aunque pueda repetir v´ertices, cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado, llamaremos ciclo a un circuito simple, es decir, un camino con extremos iguales donde el u ´nico v´ertice que se repite es el inicial como punto de llegada, llamaremos sendero c´ıclico a un sendero que es cerrado, es decir, un camino con extremos iguales donde no se repiten aristas, el v´ertice y se dice accesible desde el v´ertice x si existe un camino entre ellos. Todo v´ertice es accesible respecto a si mismo Un ciclo de longitud k se llama k–ciclo. Observad que si hay un camino entre 2 v´ertices, tambi´en habr´a un camino simple entre ellos. Definici´ on 1.1.6. Un grafo G es conexo si cada par de v´ertices est´a unido al menos por un camino. Un grafo que no es conexo se denomina desconexo. Cada grafo desconexo se puede desglosar en un n´ umero de subgrafos conexos, cada unos de los cuales es una componente conexa del grafo.

´ 1.1. DEFINICIONES BASICAS Y EJEMPLOS

7

Ejemplo: En el grafo de la izquierda, observad que no hay camino entre el v´ertice x y el v´ertice y, por lo tanto no es conexo. y

grafo no conexo 2 componentes conexas

x

grafo conexo

Definici´ on 1.1.7. Una arista de un grafo G se dice de separaci´on si G es conexo pero al suprimir la arista, se divide en dos componentes conexos Como ejemplo, el grafo del cuadro 1.2 es conexo y todas las aristas son de separaci´on.

0