O que significa 'gráfica' para uma sequência de graus?

Uma sequência de graus é gráfica se existe pelo menos um grafo simples (sem laços ou arestas múltiplas) cujos vértices têm exatamente esses graus.

O que é o Lema do Aperto de Mãos?

Ele afirma que a soma de todos os graus de vértices em qualquer grafo é sempre par, já que cada aresta contribui exatamente 2 para o total (um para cada extremidade) — portanto uma soma ímpar descarta imediatamente uma sequência como gráfica.

O que é o teorema de Erdős–Gallai?

É uma condição necessária e suficiente para que uma sequência seja gráfica: ordenada em ordem decrescente, a soma dos primeiros k termos deve ser no máximo k(k−1) mais a soma de min(dᵢ, k) para os termos restantes, para cada k de 1 a n.

Por que verificar cada valor de k?

Cada k representa um cenário potencial de 'superlotação' — verificando se os k vértices de maior grau poderiam ter arestas suficientes disponíveis (entre si e com o restante) sem exceder o que os vértices restantes podem fornecer.

O que acontece se o maior grau exceder n − 1?

Em um grafo simples com n vértices, nenhum vértice pode ter mais de n − 1 vizinhos (não pode se conectar a si mesmo nem duplicar uma aresta), então qualquer grau que exceda n − 1 torna a sequência automaticamente não gráfica.

O grafo de uma sequência gráfica é único?

Não — vários grafos diferentes podem compartilhar a mesma sequência de graus. O teorema de Erdős–Gallai apenas confirma que pelo menos um desses grafos existe, não qual deles.

Quão longa pode ser a sequência que esta calculadora consegue processar?

Esta calculadora suporta sequências de até 100 valores de comprimento, verificando todas as condições de Erdős–Gallai instantaneamente mesmo nesse tamanho.

Onde isso é usado na vida real?

É usado no design de redes e na análise de redes sociais para verificar se um conjunto proposto de contagens de conexão é sequer fisicamente realizável antes de tentar construir a rede real.

Validador de Sequência de Graus de Grafo — Verifique Se uma Sequência de Graus É Gráfica

Nosso Validador de Sequência de Graus de Grafo verifica se uma dada sequência de inteiros não negativos pode realmente ser a sequência de graus de algum grafo simples, aplicando diretamente as condições de soma de prefixos do teorema de Erdős–Gallai e informando exatamente qual condição falha se a sequência não for gráfica.

Resposta rápida

Digite uma sequência de graus abaixo para verificar instantaneamente se ela é gráfica (realizável como um grafo real) via o teorema de Erdős–Gallai.

Sequência de graus

Digite números inteiros separados por vírgulas ou espaços, ex. 3,3,2,2,1,1.

Como usar Validador de Sequência de Graus de Grafo — Teorema de Erdős–Gallai Online

1
Digite uma sequência de graus como números inteiros separados por vírgulas ou espaços, ex. 3,3,2,2,1,1.
2
Clique em 'Calcular' para verificar se a sequência é gráfica.
3
Revise a verificação passo a passo das condições de Erdős–Gallai.

Por que usar Validador de Sequência de Graus de Grafo — Teorema de Erdős–Gallai Online?

Nem toda lista de números pode ser a sequência de graus de um grafo real — o teorema de Erdős–Gallai dá um teste exato: ordene a sequência em ordem decrescente, e para cada comprimento de prefixo k, a soma dos primeiros k graus não deve exceder k(k−1) mais a soma de min(grau, k) sobre os vértices restantes. Uma sequência que passa em todas essas condições de prefixo (e tem um total par, pelo Lema do Aperto de Mãos) é garantida como realizável como um grafo simples. Esta calculadora executa essa verificação exata e informa precisamente onde ela falha, se falhar.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Matriz de Adjacência — Construa uma Matriz de Grafo Online

Construa e exiba a matriz de adjacência de um grafo a partir de uma entrada simples de lista de arestas, junto com sua sequência de graus. Calculadora gratuita, ponderada ou não ponderada.

Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online

Colora os vértices de um grafo de modo que nenhum dois nós conectados compartilhem uma cor, usando o algoritmo guloso de Welsh-Powell. Calculadora gratuita com uma entrada simples de lista de arestas.

Verificador de Grafos Planares — Teste Estilo Kuratowski Online

Verifique se um grafo é planar usando a condição necessária E ≤ 3V−6 mais uma busca explícita de subgrafos K₅/K₃,₃ para grafos pequenos. Calculadora gratuita, não é um teste de planaridade completo.