grafos

Tema 7
Grafos y árboles

7.2 Definiciones básicas de
teoría de grafos
• Un grafo G=(N,A,f ) consta de un conjunto no vacío N
denominado conjunto de nodos del grafo, un conjunto A
de aristas del grafo y una correspondencia f del conjunto
de aristas A en un conjunto de pares ordenados o
desordenados de N. si una arista se corresponde con un
par ordenado, entonces se dice que es unaarista
dirigida, en caso contrario es una arista no dirigida.
• Si una arista e ∈ A está asociada de esa forma con un
par ordenado (u,v) o con un par desordenado {u,v}, en
donde u,v ∈ N entonces se dice que la arista e conecta
o une los nodos u y v.
• Los pares de nodos que estén conectados por una arista
dentro de un grafo se denominan nodos adyacentes.

• Un grafo en el que toda arista esdirigida se denomina
digrafo o grafo dirigido.
• Un grafo en el que todas las aristas son no dirigidas se
denomina grafo no dirigido.
• Si en un grafo hay aristas dirigidas y aristas no dirigidas
se denomina mixta.
• Sea G=(N,A) y sea e ∈ A una arista dirigida asociada
al par ordenado de nodos (u,v). Se dice que la arista e
sale del nodo u o comienza en el nodo u y llega al nodo
v otermina en el nodo v.
• También se dice que los nodos
inicial y Terminal de la arista e.

u

y

v

son los nodos

• Una arista e ∈ A que conecte los nodos u y v tanto si es
dirigida como si no se dice que es incidente en los
nodos u y v.

• Una arista que conecte un nodo consigo misma se
denomina bucle o lazo.
• En algunos grafos pueden existir ciertos pares de nodos
que estén unidospor más de una arista, se denominan
aristas paralelas.
• Todo grafo que contenga aristas paralelas se denomina
multigrado.
• Existen grafos en los que los números de las aristas
muestran los pesos de éstas, se denominan grafos
ponderados.
• En un grafo un nodo que no sea adyacente a ningún
otro nodo se denominará nodo aislado.
• Un grafo que contenga solamente nodos aislados se
denominagrafo nulo.
• En un grafo dirigido, para todo nodo v el número de
aristas que tienen a v como nodo inicial se denomina
grado de salida del nodo v.

• El número de aristas que tienen a v como nodo terminal
es lo que se denomina grado de entrada y la suma del
índice de entrada y el índice de salida es lo que se
denomina grado total del nodo v.
• La suma de los grados de todos los nodos deun grafo
debe de ser un número par que será igual al doble del
número de aristas que haya en el grafo.
• Sea N(H) el conjunto de nodos de un grafo H y sea
N(G) el conjunto de nodos un grafo G tales que
N(H)⊆N(G). Si además toda arista de H es también
una arista de G, entonces se dice que el grafo H es un
subgrafo del grafo G y esto se expresa en la forma
H⊆G.
• Un grafo G=(N,A) escompleto si todos sus nodos son
adyacentes a todos los nodos del grafo, se denotan de
la forma Kn.

• Un grafo sencillo G(N,A) se denomina grafo bipartito si
N se puede descomponer en dos subconjuntos V1 y V2
tales que no haya dos nodos de V1 que sean
adyacentes ni tampoco dos nodos de V2.
• Sea G(N,A) un digrafo sencillo, toda arista de A se
puede expresar por medio de un par ordenado deelementos de N, esto es A ⊆ NxN.
• Cualquier subconjunto de NxN define una relación sobre
N.
• Un digrafo sencillo G(N,A) se denomina reflexivo,
transitivo, simétrico, antisimétrico, etc, si la relación A es
reflexiva, transitiva, simétrica, antisimétrica, etc.
• Un grafo sencillo no dirigido es antireflexivo y simétrico.
• Un digrafo sencillo G(N,A) es reflexivo, simétrico,
transitivoentonces la relación A debe ser una relación
de equivalencia sobre N y por tanto N se podrá
descomponer en clases de equivalencia.

7.3 Caminos, accesibilidad y
conexiones
• Sea G(N,A) un digrafo sencillo, se dice que una
sucesión de aristas es un camino de G si y solo si el
nodo terminal de cada arista del camino es el nodo
inicial de la próxima arista del camino, si lo hubiere.
• Un...