Grafo regular
De Wikipedia, a enciclopédia encyclopedia
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 é fortemente regular para qualquer
.
Um teorema de Nash-Williams diz que cada k‑grafo regular em 2k + 1 vértices tem um ciclo hamiltoniano.
- grafo 0-regular
- grafo 1-regular
- grafo 2-regular
- grafo 3-regular