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”
G2
Sin duda 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
No hay comentarios:
Publicar un comentario