Grau (teoria dos grafos): diferenças entre revisões

Na [[teoria dos grafos]], o '''grau''' (ou '''valência''') de um [[Vértice (teoria dos grafos)| vértice]] de um grafo é o número de [[grafo|arestas]] [[grafo|incidentes]] para com o vértice, com os [[laço (teoria dos grafos)|laços]] contados duas vezes. <ref name="diestel>{{Citar livro| sobrenome=Diestel | Nome=Reinhard | title=Graph Theory | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | editora=Springer-Verlag | local=Berlin, New York | edição=3ª | isbn=978-3-540-26183-4 | ano=2005}}.</ref><ref name=even>{{Referência a livro|autor=Even, Shimon|título=Graph Algorithms|subtítulo=|idioma=|edição=|local=Rockville, Maryland|editora=Computer Science Press|ano=1979|páginas=249|volumes=|volume=|id=ISBN 0-914894-21-8}}</ref> Ou de forma análoga, o número de vértices adjacentes a ele.<ref name=szwarcfiter>{{Referência a livro|autor=Szwarcfiter, Jayme Luiz|título=Grafos e algoritmos computacionais|subtítulo=|idioma=|edição=|local=Rio de Janeiro|editora=Campus|ano=1988|páginas=|volumes=|volume=|id=ISBN 85-7001-341-8}}</ref>O grau de um vértice <math>v</math> é denotado <math>\deg(v).</math> O grau máximo de um grafo ''G'', denotado por Δ(''G''), e o grau mínimo de um grafo, denotado por δ(''G''), são os graus máximos e mínimos de seus vértices. No grafo à direita, o grau máximo é 3 e o mínimo é 0. Em um [[grafo regular]], todos os graus são os mesmos, e assim podemos falar de ''o'' grau do gráfico.