En matem\u00e1ticas y ciencias de la computaci\u00f3n, un grafo (del griego grafos: dibujo, imagen)\u200b es un conjunto de objetos llamados v\u00e9rtices o nodos unidos por enlaces llamados aristas o arcos, \\(G=(V,\\mathcal{E})\\), que permiten representar relaciones binarias entre elementos de un conjunto.\n<\/p><\/blockquote>\n
Nosotros trabajaremos con grafos donde \\(0<|V|\\) y finito; sin embargo, el cardinal de \\(\\mathcal{E}\\) puede ser cero. Si \\(V=\\{v_1,\\ldots,v_2\\}\\) todo elemento de \\(e\\in \\mathcal{E}\\) es un par de elementos de \\(V\\); es decir \\(e=\\{v_i,v_j\\}\\) para \\(v_i,v_j\\in V\\). Al elemento \\(\\{v_i,v_j\\}\\in \\wp(V)\\) se le denomina par no ordenado; as\u00ed \\(\\mathcal{E}\\subseteq \\{x\\in {\\wp}(V):|x|=2\\}\\) es un conjunto de pares.<\/p>\n
Generalmente tratamos como grafo al conjunto anterior, pero si queremos ser precisos deber\u00edamos decir grafo no dirigido.<\/p>\n
Se llama orden<\/strong> del grafo \\(G=(V,\\mathcal{E})\\) a su n\u00famero de v\u00e9rtices, \\({\\displaystyle |V|}\\).<\/p>\nEl grado de un v\u00e9rtice<\/strong> en un grafo es el n\u00famero de aristas incidentes a \u00e9l. En un grafo dirigido, se puede distinguir entre grado de salida (\u00aboutdegree\u00bb, n\u00famero de arcos que salen del v\u00e9rtice) y grado de entrada (\u00abindegree\u00bb, n\u00famero de arcos que llegan al v\u00e9rtice); un v\u00e9rtice fuente es un v\u00e9rtice con grado de entrada cero, mientras que un sumidero es un v\u00e9rtice con grado de salida cero.<\/p>\nLlamamos grado de un grafo<\/strong> a la suma de los grados de todos sus v\u00e9rtices.<\/p>\nUn bucle <\/strong>es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.<\/p>\nProposici\u00f3n:<\/strong> Dado un grafo \\(G:(V,\\mathcal{E})\\) \\[\\mathbf{gr}(G)=2|\\mathcal{E}|\\]<\/p><\/blockquote>\n<\/p>\n
Ejercicio<\/strong>: Determinar el grado del grafo <\/p>\n