Definições Básicas
Um grafo é um tipo especial de digrafo, também conhecido como grafo não-dirigido e grafo não-orientado. Um grafo é um digrafo simétrico. Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v.
Convém tratar esse par de arcos com distinção. Assim, diremos que um par de arcos anti-paralelos é uma aresta (= edge). As pontas dos dois arcos são as pontas da aresta. As duas pontas de uma aresta são indistinguíveis: não há ponta inicial nem ponta final.
Uma aresta com pontas v e w será denotada, indiferentemente, por v-w ou w-v.
Diremos que uma aresta v-w liga os vértices v e w. Diremos também que v-w incide em v e em w. O número de arestas de um grafo é a metade do seu número de arcos. Se E denota o número de arestas e A denota o número de arcos então A = 2•E.
Graus de vértices
O grau de um vértice em um grafo é o número de arestas que incidem no vértice. Esse número é igual ao grau de entrada do vértice e também ao grau de saída do vértice.
É fácil verificar que a soma dos graus de todos os vértices de um grafo vale 2E, sendo E o número de arestas. Portanto, o grau médio do grafo é o número 2E/V , sendo V o número de vértices.
Convém lembrar que um vértice é isolado se o seu grau é nulo.
Número máximo de arestas
Quantas arestas, no máximo, tem um grafo com V vértices? Não é difícil verificar que a resposta é V•(V-1)/2. Esse número é pouco menor que ½ V^2.
Um grafo é completo se todo par não-ordenado de vértices distintos é um aresta. Um grafo completo com V vértices tem exatamente V•(V-1)/2 arestas.
Baseado no site do IME.
Um grafo é um tipo especial de digrafo, também conhecido como grafo não-dirigido e grafo não-orientado. Um grafo é um digrafo simétrico. Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v.
Convém tratar esse par de arcos com distinção. Assim, diremos que um par de arcos anti-paralelos é uma aresta (= edge). As pontas dos dois arcos são as pontas da aresta. As duas pontas de uma aresta são indistinguíveis: não há ponta inicial nem ponta final.
Uma aresta com pontas v e w será denotada, indiferentemente, por v-w ou w-v.
Diremos que uma aresta v-w liga os vértices v e w. Diremos também que v-w incide em v e em w. O número de arestas de um grafo é a metade do seu número de arcos. Se E denota o número de arestas e A denota o número de arcos então A = 2•E.
Graus de vértices
O grau de um vértice em um grafo é o número de arestas que incidem no vértice. Esse número é igual ao grau de entrada do vértice e também ao grau de saída do vértice.
É fácil verificar que a soma dos graus de todos os vértices de um grafo vale 2E, sendo E o número de arestas. Portanto, o grau médio do grafo é o número 2E/V , sendo V o número de vértices.
Convém lembrar que um vértice é isolado se o seu grau é nulo.
Número máximo de arestas
Quantas arestas, no máximo, tem um grafo com V vértices? Não é difícil verificar que a resposta é V•(V-1)/2. Esse número é pouco menor que ½ V^2.
Um grafo é completo se todo par não-ordenado de vértices distintos é um aresta. Um grafo completo com V vértices tem exatamente V•(V-1)/2 arestas.
Baseado no site do IME.
