pt.wikipedia.org

Grafo regular – Wikipédia, a enciclopédia livre

Origem: Wikipédia, a enciclopédia livre.

Famílias de grafos definidos por seus automorfismos
distância-transitivo{\displaystyle \rightarrow }distância-regular{\displaystyle \leftarrow }fortemente regular
{\displaystyle \downarrow }
simétrico (arco-transitivo){\displaystyle \leftarrow }t-transitivo, t ≥ 2.
{\displaystyle \downarrow }
(se conectado)
transitivo nos vértices e nas arestas{\displaystyle \rightarrow }aresta-transitivo e regular{\displaystyle \rightarrow }aresta-transitivo
{\displaystyle \downarrow }{\displaystyle \downarrow }
vértice-transitivo{\displaystyle \rightarrow }regular
{\displaystyle \uparrow }
grafo de Cayleyantissimétricoassimé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 {\displaystyle K_{m}} é fortemente regular para qualquer {\displaystyle m}.

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

  • grafo 0-regular

    grafo 0-regular

  • grafo 1-regular

    grafo 1-regular

  • grafo 2-regular

    grafo 2-regular

  • grafo 3-regular

    grafo 3-regular

Seja A a matriz de adjacência de um grafo. Então, o grafo é regular se e somente se {\displaystyle {\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 {\displaystyle {\textbf {j}}}, assim como para tais autovetores {\displaystyle v=(v_{1},\dots ,v_{n})}, nós temos {\displaystyle \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 (1997). Graph theory and its engineering applications. [S.l.]: World Scientific. 29 páginas. 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.