Una formulación equivalente del problema de isomorfismo de grafos Reportar como inadecuado




Una formulación equivalente del problema de isomorfismo de grafos - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.



El problema de encontrar un invariante que caracterice el conjunto de grafos isomorfos a un grafo dado, es un problema clásico en teoría de grafos. No se conoce un conjunto completo de invariantes para un grafo 1,p.11.En esta nota presentamos, de manera intuitiva; una solución de este problema

Tipo de documento: Artículo - Article

Palabras clave: Conjunto de grafos isomorfos, matriz de adyacencia, designación de vértices





Fuente: http://www.bdigital.unal.edu.co


Introducción



22 Boletin de Matematicas Vol.
XVIII N9.
1~2~3~ (l984) iAPORTES UNA FORMULACION EQUIVALENTE DEL PROBLEMA DE ISOMORFISMO DE GRAFOS 0-6vacdo SWJvc., VLet.on: Medcna , T atian.a. El problema que caracterice de encontrar el conjunto Lao cxuu» . un invariante de grafos isomor- fos a un grafo dado, es un problema en teorla completo de grafos. No se conoce de invariantes de manera [l,p.i~. intuitiva; de este problema. Un grafo dirigido donde un conjunto para un grafo En esta nota presentamos, una solucion clasico es una tripla G = (V;E;f) V y E son conjuntos finitos y ~ es una funcion uno a uno que hace corresponder da elemento mentos de de E una pareja Geometricamente, ordenada a ca- de ele- E es el conjun- 23 aportes ado s (f 1 echas ), V e s e1 con j un t 0 d ever t 0 del tices (nodos) y la aplicacion lado sus vertices cion del lado. Figura v = de acuerdo Para el grafo ~ asigna con a cada la orienta- dirigido de la 1, tenernos: E = {a.,b,c.,d,e,n,g,h,i}, {1,2,3,4,5}, f(a.) = (1,2), ~(d) = (3,2), PCe) = P( g) = (5, P( h) 3 ), f( = b) = (2,1), 15( = c) (2,4), f(n) = (3, P ( i) 5 ), = (2,2), (3,4), (5, 5) . 4 FigU1~a 1 Un grafo G puede tarnbien representarse apOltes 24 par media de yaeene~a. las V una Para vertices = {1,2, abtener del ,n}, ••• matriz, esta grafa mat~~z de a~ llamada matriz empezanda numeramas en 1. Si definimas 1 , si existe una flecha que va del vertice ~ al vertice j. a·· - -j = 0, en casa cantraria. La matrLz de adyacencia grafa de la Figura Vi V2 V3 V4 Vs Es claro un grafo numeren dado los vertices Figura del ° 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 que grafo 2, obtenemos yacencia: la matriz depende par al 1 es vertices de v~~t~ee~); correspondiente (1) de adyaceneia de la manera del ejemplo, grafo como la siguiente se (de~~gnae~6n si numeramos de la Figur...






Documentos relacionados