Grafos, Disgrafos y Multigrafos
Enviado por Programa Chuletas y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 2,46 KB
2.1. Grafos, Disgrafos y Multigrafos
Los grafos pueden ser considerados diagramas o dibujos, o formalmente como un par de
conjuntos.
Un grafo G se define como un conjunto E de pares no ordenados de elementos distintos
y otro conjunto de elementos V.
El conjunto V es el conjunto de vértices del grafo, se denota por V(G).
El conjunto E es el conjunto de aristas del grafo, se denota por E(G).
G=(V, E)
V={v 1 , v 2 ,..., v n}
E={v i v j , v n ,v m ,...}
Dos vértices v i, v j son adyacentes si son los extremos de una arista, es decir, si el par de
vértices V es un elemento de E.
V={v 1 , v 2 , v 3}
E={v 1 v 2 , v 2 v 3 , v 1 v 3}
#V es el número de vértices.
#E es el número de aristas.
Un grafo es finito si #V es finito.
Multigrafo: es un grafo con varias aristas entre dos vértices.
V={v 1 , v 2 , v 3}
E={v 1 v 2 , v 2 v 3 , v 2 v 3 , v 1 v 3 , v 1 v 3}
Pseudografo: tiene aristas cuyos extremos coinciden (origen y fin en el mismo vértice),tales aristas se denominan lazos.
V={v 1 , v 2 , v 3}E={v 1 v 1 , v 1 v 2 , v 2 v 2 , v 1 ,v 3}
Digrafo (grafo dirigido): A cada arista se le asigna un orden en sus extremos, en el dibujo se indica con una flecha. Los pares que forman los elementos de E estánordenados.
V={v 1 , v 2 , v 3}E={v 1 v 2 , v 2 v 3 , v 3 v 1}
Los grafos pueden ser considerados diagramas o dibujos, o formalmente como un par de
conjuntos.
Un grafo G se define como un conjunto E de pares no ordenados de elementos distintos
y otro conjunto de elementos V.
El conjunto V es el conjunto de vértices del grafo, se denota por V(G).
El conjunto E es el conjunto de aristas del grafo, se denota por E(G).
G=(V, E)
V={v 1 , v 2 ,..., v n}
E={v i v j , v n ,v m ,...}
Dos vértices v i, v j son adyacentes si son los extremos de una arista, es decir, si el par de
vértices V es un elemento de E.
V={v 1 , v 2 , v 3}
E={v 1 v 2 , v 2 v 3 , v 1 v 3}
#V es el número de vértices.
#E es el número de aristas.
Un grafo es finito si #V es finito.
Multigrafo: es un grafo con varias aristas entre dos vértices.
V={v 1 , v 2 , v 3}
E={v 1 v 2 , v 2 v 3 , v 2 v 3 , v 1 v 3 , v 1 v 3}
Pseudografo: tiene aristas cuyos extremos coinciden (origen y fin en el mismo vértice),tales aristas se denominan lazos.
V={v 1 , v 2 , v 3}E={v 1 v 1 , v 1 v 2 , v 2 v 2 , v 1 ,v 3}
Digrafo (grafo dirigido): A cada arista se le asigna un orden en sus extremos, en el dibujo se indica con una flecha. Los pares que forman los elementos de E estánordenados.
V={v 1 , v 2 , v 3}E={v 1 v 2 , v 2 v 3 , v 3 v 1}