miniatura| Un grafo non orientado onde se indicou o grao de cada vértice. Neste grafo, o grao máximo é e o grao mínimo é . En matemáticas, e máis concretamente na teoría de grafos, o grao (ou valencia) dun vértice dun grafo é o número de ligazóns (arestas ou arcos) que conectan este vértice, onde os bucles contan dúas veces. O grao dun vértice nótase .
Gráfico orientado No caso dun grafo orientado, tamén se fala do grao de entrada dun vértice , é dicir, o número de arcos orientados cara ao vértice , e o grao de saída do vértice , é dicir, o número de arcos que saen de . Temos : o grao do vértice é a suma do grao saínte e o grao entrante.
Características O grao máximo dun grafo , denótase , e o grao mínimo do grafo, denótase , son respectivamente o máximo e o mínimo dos graos dos seus vértices. Nun grafo regular, todos os vértices teñen o mesmo grao, polo que podemos falar do grao do grafo.
Notas
Véxase tamén
Bibliografía
Outros artigos Grafo
Categoría:Teoría de grafos