Isomorfismo de Grafos

ISOMORFISMO DE GRAFOS

ISOMORFISMO DE GRAFOS

Las siguientes instrucciones se dan a dos personas que no pueden ve el papel de la otra:

Dibuje y etiquete 5 vértices: a, b, c, d, e.

Conecte:  “a-b, b-c, c-d, d-e, e-a”

 

 Las gráficas producidas se aprecian en la siguiente fig.

 G1

G2

Estas figuras definen la misma grafica a un cuando aparecesca diferentes,  se dicen que estas graficas son isoformas, las graficas G1 y G2  son Isoformas si existe función f 1º1, sobre los vértices de G1 alas aristas de G2 pero es incidente en w en G1 si solo si, la arista G (n) es existente en f(v) , f(w) G2. El par de funciones  f y g reciben el nombre de isoformofismo de G1 y G2.

 GRAFICAS PLANAS

3 ciudades C1,C2,C3 deberían conectarse en forma directa mediante autopistas con cada una de otras 3 ciudades C4,C5,C6.

 Puede diseñarse un sistema de carretera de manera que las autopistas no se crucen, la fig. anterior ilustra un sistema donde las aristas se cruzan.

Una grafica plana se puede dibujar en el plano sin que sus aristas se crucen. Al diseñar circuitos impresos es decible tener el menor de cruces posibles, así el diseñador de circuitos impresos se enfrentan con el problema de graficas planas.

Si una grafica plana conexo se dibuja en el plano , esto se divide en regiones continuas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Ejemplo en la siguiente grafica la cara A tiene como limite el ciclo (5,2,3,4,5) . B tiene el  ciclo (1,2,5,1), la cara anterior D se considera limitada por el ciclo (1,2, 3,4,6,1). La grafica de la figura tiene 4 caras  e igual  8 aristas y 6 vértices.

F= 4 varas

E= 8 aristas

V= 6 vértices

F= E –V +2

F= 8-6+2

F = 2