El código de G usando X ha sido definido de varias maneras. En adelante, explicaremos dos maneras de construir este código. La primera variante ubica las etiquetas de los vértices y luego adiciona las filas de la sub matriz estrictamente triangular inferior(la matriz triangular inferior excluyendo la diagonal).
Un mismo grafo puede tener varias matrices de adyacencias ya que existe una dependencia con el orden de los vértices que se utilizo durante la construcción de la matriz. Caracterizar un grafo etiquetado requiere de una representación que sea única en dicho grafo y en todos aquellos que son isomorfos con este. Es por eso que se define la matriz de adyacencia canónica a partir del código de la matriz.Es cuando se acepta mas de un arco uniendo dos vértices. En términos formales, no son grafos. Un multígrafo es un grafo que consta de segmentos múltiples y lazos.
Es la asignación de etiquetas, tradicionalmente representada mediante enteros, alas aristas o vértices, o ambos, de un grafo.
Formalmente, dado un grafo G, un vértice etiquetado es una función que corresponde a vértices de G aun conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de etiquetas. En este caso, G es llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado(p.e. los números reales), esta puede ser llamado como grafo ponderado.
Es una tétrada {V, E, L, I}, donde:
· * V es un conjunto cuyos elementos son llamados vértices.
· *E c {e| e c V, |e| = 2} es un conjunto cuyos elementos son llamados aristas( cada arista es un conjunto de vértices con cardinalidad dos).
· *L es el conjunto de etiquetas
*I: V U e -> L es una función que asigna etiquetas a los vértices y aristas del grafo.
Se dice que un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista que los une.
El conjunto de los grafos completos es denominado usualmente k, es decir, grafo completo de n vértices tiene exactamente {n(n-1)}/2 aristas.
