Digrafos
Um digrafo (= um grafo direcionado) consiste em dois conjuntos: um conjunto vértices e outro de arestas. Cada aresta é um par ordenado de vértices. O primeiro vértice é o início e o segundo é o fim da aresta.
Uma aresta com início em v e final em w será denotado por v-w (isto não é uma subtração). Existir uma aresta que liga o vértice v ao vértice w não significa que existe uma aresta que liga o vértice w ao vértice v.
Se v-w existe então dizemos que w é vizinho (ou adjacente) de v.
Digrafos simétricos
Um digrafo é simétrico se cada um de suas arestas é anti-paralela* a alguma outra aresta.
*arestas anti-paralelas: Para uma aresta v-w, temos também uma aresta w-v, estas duas arestas são anti-paralelas.
Grau de entrada e de saída
O grau de saída de um vértice v em um digrafo é o número de arestas que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arestas que terminam em .
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).
Número de arestas
Qual máximo de arestas em um dígrafo de V vértices? Não é difícil verificar que a resposta a essa pergunta é o produto V•(V-1). Para valores grandes de V, esse número é apenas um pouco menor que V^2.
Um digrafo é completo se todo par ordenado de vértices distintos tem uma aresta entre eles (Sendo E número de arestas e V número de vértices, para um dígrafo completo: E = V•[V-1]).
Um digrafo é denso se o seu número de arestas é proporcional ao quadrado do número de vértices.
Um digrafo é esparso se for o complemento de um digrafo denso, ou seja, se o número de pares ordenados de vértices que não são arestas for proporcional ao quadrado do número de vértices.
Baseado no site do IME.
Um digrafo (= um grafo direcionado) consiste em dois conjuntos: um conjunto vértices e outro de arestas. Cada aresta é um par ordenado de vértices. O primeiro vértice é o início e o segundo é o fim da aresta.
Uma aresta com início em v e final em w será denotado por v-w (isto não é uma subtração). Existir uma aresta que liga o vértice v ao vértice w não significa que existe uma aresta que liga o vértice w ao vértice v.
Se v-w existe então dizemos que w é vizinho (ou adjacente) de v.
Digrafos simétricos
Um digrafo é simétrico se cada um de suas arestas é anti-paralela* a alguma outra aresta.
*arestas anti-paralelas: Para uma aresta v-w, temos também uma aresta w-v, estas duas arestas são anti-paralelas.
Grau de entrada e de saída
O grau de saída de um vértice v em um digrafo é o número de arestas que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arestas que terminam em .
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).
Número de arestas
Qual máximo de arestas em um dígrafo de V vértices? Não é difícil verificar que a resposta a essa pergunta é o produto V•(V-1). Para valores grandes de V, esse número é apenas um pouco menor que V^2.
Um digrafo é completo se todo par ordenado de vértices distintos tem uma aresta entre eles (Sendo E número de arestas e V número de vértices, para um dígrafo completo: E = V•[V-1]).
Um digrafo é denso se o seu número de arestas é proporcional ao quadrado do número de vértices.
Um digrafo é esparso se for o complemento de um digrafo denso, ou seja, se o número de pares ordenados de vértices que não são arestas for proporcional ao quadrado do número de vértices.
Baseado no site do IME.
