Ejemplo:
Matriz de adyacencia Grafo no dirigido
Matriz de adyacencia

Dado un grafo etiquetado G = {V, E, L, I} tal que |V| = n y una permutación de los vértices en V = { v0, v1,…, vn-1}, la matriz de adyacencia de G respecto a dicha permutación es X = (xij)ij ^n-1 donde:



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.
Multígrafo

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.

También es un grafo en el que hay pares de vértices unidos por mas de una arista, es decir, que tiene aristas múltiples.
Grafo etiquetado

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.

Grafo completo

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.



  • Happy Halloween
    Get your Twitter to look nice with aCustom Twitter Backgrounds

    signo

    Aquarius
    Make your Twitter look amazing withFree Twitter Backgrounds

    u_u

    Seguidores

    WIKI

    REPRODUCTOR