OCTAVO SEMESTRE | LICENCIATURA EN MATEMÁTICAS
Entonces el grafo
𝐺 = (𝑉, 𝐴) tiene a 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 𝑦 𝑣5 como vértices y sus aristas son
𝑣1 𝑣2 , 𝑣1 𝑣3 , 𝑣1 𝑣4 , 𝑣2 𝑣4 𝑦 𝑣2 𝑣5 .
Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos correspondientes mediante una linea. FIGURA 10. REPRESENTACIÓN GRÁFICA DE UN GRAFO
El grafo de la figura 10 tiene como conjunto de vértices 𝑉 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 } siendo su conjunto 𝐴 = {𝑣1 𝑣2 , 𝑣2 𝑣3 , 𝑣2 𝑣5 , 𝑣3 𝑣4 , 𝑣3 𝑣5 }
de
aristas,
adyacentes:
𝑣1 𝑦 𝑣2 , 𝑣2 𝑦 𝑣3 , 𝑣2 𝑦 𝑣5 , 𝑣3 𝑦 𝑣4 , 𝑣3 𝑦 𝑣5 .
Vértices
Vértices
no
adyacentes:
𝑣1 𝑦 𝑣3 , 𝑣1 𝑦 𝑣4 , 𝑣2 𝑦 𝑣4 , 𝑣4 𝑦 𝑣5 .
En la sección anterior, hemos representado los grafos mediante un esquema o un diagrama. Algunas veces, como por ejemplo cuando se desea analizar un grafo por ordenador es necesaria una representación más formal. (González Gutiérrez, 2004).
3.4.1.1 Matriz de Adyacencia 𝑆𝑒𝑎 𝐺 𝑢𝑛 𝑔𝑟𝑢𝑝𝑜 𝑐𝑢𝑦𝑜 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑣é𝑟𝑡𝑖𝑐𝑒𝑠 𝑒𝑠 𝑉 = {𝑣1 , 𝑣2 , … 𝑣𝑝 }. 𝐿𝑙𝑎𝑚𝑎𝑟𝑒𝑚𝑜𝑠 𝑚𝑎𝑡𝑟𝑖𝑧 𝑑𝑒
𝑎𝑑𝑦𝑎𝑐𝑒𝑛𝑐𝑖𝑎 𝑑𝑒𝑙 𝑔𝑟𝑎𝑓𝑜 𝐺 𝑎 𝑙𝑎 𝑚𝑎𝑡𝑟𝑖𝑧 𝐴 = (𝑎𝑖𝑗 ) 𝑑𝑒 𝑝 − 𝑓𝑖𝑙𝑎𝑠 𝑦 𝑝 − 𝑐𝑜𝑙𝑢𝑚𝑛𝑎𝑠, 𝑑𝑜𝑛𝑑𝑒 𝑎𝑖𝑗 = {
1 𝑠𝑖 𝑣𝑖 𝑦 𝑣𝑗 𝑠𝑜𝑛 𝑎𝑑𝑦𝑎𝑐𝑒𝑛𝑡𝑒𝑠 0 𝑠𝑖 𝑣𝑖 𝑦 𝑣𝑗 𝑛𝑜 𝑠𝑜𝑛 𝑎𝑑𝑦𝑎𝑐𝑒𝑛𝑡𝑒𝑠
Ejemplo: Realizar la matriz de adyacencia usando la información que se tiene en el grafo a)
32 UnADM | DCEIT| PT2
