grafo regular

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 e o de cada vértice sejam iguais uns aos outros. 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 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