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}

Entradas relacionadas: