Definición
Dado un
grafo simple G = (V, E) con n=|V| vértices {v1,...,vn} y m=|E|
aristas {e1,...,em}, su
matriz de incidencia es la matriz
de orden nxm, B(G)=(bij), donde bij=1 si
Vi es incidente con ej y bij=0 en caso contrario. La matriz de incidencia sólo
contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada
columna tiene exactamente dos unos. El número de unos que aparece en cada fila
es igual al grado del vértice correspondiente. Una fila compuesta sólo por
ceros corresponde a un vértice aislado.
La matriz de
incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide
exactamente en dos vértices, cada columna tiene exactamente dos unos. El número
de unos que aparece en cada fila es igual al grado del vértice correspondiente.
Una fila compuesta sólo por ceros corresponde a un vértice aislado.
• Grado de
incidencia positivo: El grado de incidencia positivo de un nodo nj es el número
de arcos que tienen como nodo inicial a nj. Ejemplo: El grado de incidencia de
1 es igual a 3.
• Grado de
incidencia negativo: El grado de incidencia negativo de un nodo nj es el número
de arcos que terminan en nj. Ejemplo: El grado de incidencia negativo de 1 es
igual a 1.
• Grado de
un nodo: Para dígrafos es el grado de incidencia positivo menos el grado de
incidencia negativo del nodo. Ejemplo: El grado de 1 es igual a 3 –1 = 2, el
grado del nodo 4 es 2 –2 = 0. Para grafos no dirigidos es el número de líneas
asociadas al nodo.
0 comentarios:
Publicar un comentario