Como usar o Teorema de Euler para encontrar o número de arestas
Leonhard Euler foi um matemático suíço do século 18, que , entre outras coisas, fez uma certa quantidade de pesquisa em teoria dos grafos . Ele descreve a relação entre o número de fios , o número de vértices , e o número de faces em um gráfico planar . Existem algumas limitações associadas a esta , principalmente que as bordas não podem cruzar , mas é um teorema poderoso e frequentemente usado em teoria dos grafos . Instruções
1
Determine o número de faces no gráfico. Estes são os espaços definidos por um conjunto de arestas . Usando um mapa analogia , se as bordas estão as fronteiras entre os países , então os caras são os países . Isto pode ser fornecido a você no problema , ou você pode ter para determiná-lo a partir de relacionamentos. Note que isso inclui o rosto ilimitada infinito , que é a extensão externa para todas as arestas .
2
Determine o número de vértices. Em um grafo planar , as bordas não estão autorizados a cruzar , mas eles estão autorizados a atender a pontos chamados vértices.
3
Adicione o número de faces e vértices . Em seguida, subtrair dois a partir desta quantidade. Supondo que o seu gráfico atende a todos os critérios exigidos , o mais importante que é planar , então este é o número de arestas fórmula
de Euler : . Bordas + ‘ vértices enfrenta = 2
