Grafos
Los grafos pueden ser considerados diagramas o dibujos, o formalmente como un par de
conjuntos.
Un grafo G se define como un conjunto E de pares no ordenados de elementos distintos
y otro conjunto de elementos V.
El conjunto V es el conjunto de vértices del grafo, se denota por V(G).
El conjunto E es el conjunto de aristas del grafo, se denota por E(G).
G=(V, E)
V={v1, v2,..., vn}
E={vivj, vn,vm,...}
Dos vértices vi, vj son adyacentes si son los extremos de una arista, es decir, si el par de
vértices V es un elemento de E.
El numero de V es el número de vértices.
El numero de E es el número de aristas.
Un grafo es finito si Numero de V es finito.
Isomorfismo
- Los grafos simples G1 = (V1, E1) y G2 = (V2, E2) son isomorfos
- si hay una función biyectiva f desde V1 a V2 con la propiedad
- que a y b son adyacentes en G1 si y solo si f (a) y f (b) son
- adyacentes en G2, para todo a y b en V1.
- Tal función f es llamada un isomorfismo (igual forma).
Para mostrar que 2 grafos no son isomorfos podemos mostrar
que sus invariantes (propiedad que los grafos simples deben
cumplir) no son iguales.
1. El numero de vértices.
2. El número de aristas.
3. El grado de los vértices.
Si en alguna de esas cantidades difieren 2 grafos simples, no
son isomorfos.
Nota: Si sus invariantes son los mismos, no necesariamente
son isomorfos.
Definiciones de grafos dirigidos y no dirigidos
Grafos Dirigidos: Un conjunto de vértices junto con un conjunto de aristas dirigidas que conectan a estos vértices entre si.
Grafos no Dirigidos: Un conjunto de vértices junto con un conjunto de aristas no dirigidas que conectan a estos vértices entre si.
GRAFOS DIRIGIDOS
Un grafo dirigido es un grafo cuyas aristas son todas dirigidas (arcos).
GRAFOS NO DIRIGIDOS
De la misma manera que los no dirigidos, les podemos notar:
G = (V , A)
Un arco (v, w) difiere de (w, v)
Si G es simple, |A| ≤ |V |(|V | − 1)
Muchos grafos posibles con |V | aristas:
2|V |(|V |−1)
El grafo inverso es el grafo que se obtiene al cambiar la dirección de todos los arcos
La explicacion se esta apollanda con un video realizado por los estudiantes de la universidad
central de colombia.
BIBLIOGRAFIA
http://www.terra.es/pv_obj_cache/pv_obj_id_CB3851A1A51DE34FD365DE13460CC402B9880100/filename/teoria%20de%20grafos.pdf
|
