Grafo regular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Famílias de grafos definidos por seus automorfismos
distância-transitivo \rightarrow distância-regular \leftarrow fortemente regular
\downarrow
simétrico (arco-transitivo) \leftarrow t-transitivo, t ≥ 2 .
\downarrow
(se conectado)
transitivo nos vértices e nas arestas \rightarrow aresta-transitivo e regular \rightarrow aresta-transitivo
\downarrow \downarrow
vértice-transitivo \rightarrow regular
\uparrow
grafo de Cayley anti-simétrico assimétrico


Em Teoria dos grafos, um grafo regular é um grafo onde cada vértice tem o mesmo número de adjacências, i.e. cada vértice tem o mesmo grau ou valência. Um grafo direcionado regular também deve satisfazer a condição mais forte de que o grau de entrada e o grau de saída de cada vértice sejam iguais uns aos outros.[1] Um grafo regular com vértices de grau k é chamado um grafo k‑regular ou grafo regular de grau k.

Grafos regulares de grau no máximo 2 são fáceis de classificar: Um grafo 0-regular é composto por vértices desconectados, um grafo 1-regular consiste de arestas desconectadas, e um grafo 2-regular consiste de ciclos desconectados.

Um grafo 3-regular é conhecido como um grafo cúbico.

Um grafo fortemente regular é um grafo regular, onde cada par de vértices adjacentes tem o mesmo número l de vizinhos em comum, e cada par de vértices não-adjacentes tem o mesmo número n de vizinhos em comum. Os menores grafos que são regulares, mas não fortemente regulares são os grafos ciclos e os grafos circulantes em 6 vértices.

O grafo completo K_m é fortemente regular para qualquer m.

Um teorema de Nash-Williams diz que cada k‑grafo regular em 2k + 1 vértices tem um ciclo hamiltoniano.

Propriedades algébricas[editar | editar código-fonte]

Seja A a matriz de adjacência de um grafo. Então, o grafo é regular se e somente se \textbf{j}=(1, \dots ,1) é um autovetor de A..[2] Seu autovalor será o grau constante do grafo. Autovetores correspondentes a outros autovalores são ortogonais a \textbf{j}, assim como para tais autovetores v=(v_1,\dots,v_n), nós temos \sum_{i=1}^n v_i = 0.

Um grafo regular de grau k é conectado se e somente se o autovalor k tem uma multiplicidade 1.[2]

Referências

  1. Chen, Wai-Kai. Graph theory and its engineering applications. [S.l.]: World Scientific, 1997. 29 pp. ISBN 978-981021859-1.
  2. a b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.

Ligações externas[editar | editar código-fonte]

  • GenReg software e dados por Markus Meringer.