Para entender o grau de entrada e de saída de um vértice, precisamos primeiro aprender sobre o conceito de grau de um vértice. Depois disso, podemos entender facilmente o grau de entrada e de saída de um vértice. Devemos saber que o grau de entrada e o grau de saída só podem ser determinados no gráfico direcionado. Podemos calcular o grau de um vértice com a ajuda de um gráfico não direcionado. No gráfico não direcionado, não podemos calcular o grau de entrada e o grau de saída de um vértice.
Grau de um vértice
Se quisermos encontrar o grau de cada vértice de um grafo, neste caso, temos que contar o número de relações que são estabelecidas por um determinado vértice com o outro vértice. Em outras palavras, podemos determinar o grau de um vértice calculando o número de arestas que se conectam a esse vértice. O grau de um vértice é indicado com a ajuda de deg(v). Se houver um gráfico simples, que contém n número de vértices, neste caso, o grau de qualquer vértice será:
Deg(v) = n-1 ∀ v ∈ G
Um vértice tem a capacidade de formar uma aresta com todos os outros vértices de um gráfico, exceto ele mesmo. Portanto, em um gráfico simples, o grau de um vértice será determinado pelo número de vértices em um gráfico menos 1. Aqui 1 é usado para o próprio vértice porque ele não faz um loop sozinho. Se o gráfico contiver os vértices que possuem o auto-loop, então esse tipo de gráfico não será um gráfico simples.
Exemplo:
Neste exemplo, temos um gráfico que possui 6 vértices, ou seja, a, b, c, d, e e f. O vértice 'a' tem grau 5 e todos os outros vértices têm grau 1. Se qualquer vértice tiver grau 1, então esse tipo de vértice será conhecido como 'vértice final'.
java substitui tudo
Existem dois casos de gráficos em que podemos considerar o grau de um vértice, que são descritos a seguir:
- Gráfico não direcionado
- Gráfico direcionado
Agora aprenderemos detalhadamente o grau de um vértice em um gráfico direcionado e o grau de um vértice em um gráfico não direcionado.
Grau de um vértice em um gráfico não direcionado
Se houver um gráfico não direcionado, então neste tipo de gráfico não haverá aresta direcionada. Os exemplos para determinar o grau de um vértice em um gráfico não direcionado são descritos a seguir:
Exemplo 1: Neste exemplo, consideraremos um gráfico não direcionado. Agora descobriremos o grau de cada vértice nesse gráfico.
Solução: No gráfico não direcionado acima, há um total de 5 números de vértices, ou seja, a, b, c, d e e. O grau de cada vértice é descrito a seguir:
- O gráfico acima contém 2 arestas, que se encontram no vértice 'a'. Portanto, Graus (a) = 2
- Este gráfico contém 3 arestas, que se encontram no vértice 'b'. Portanto, Graus (b) = 3
- O gráfico acima contém 1 aresta, que se encontra no vértice 'c'. Portanto, Deg(c) = 1. O vértice c também é conhecido como vértice pendente.
- O gráfico acima contém 2 arestas, que se encontram no vértice 'd'. Portanto, Grau(d) = 2.
- O gráfico acima contém 0 arestas, que se encontram no vértice 'e'. Portanto Deg(a) = 0. O vértice e também pode ser chamado de vértice isolado.
Exemplo 2: Neste exemplo, consideraremos um gráfico não direcionado. Agora descobriremos o grau de cada vértice nesse gráfico.
Solução: No gráfico não direcionado acima, há um total de 5 números de vértices, ou seja, a, b, c, d e e. O grau de cada vértice é descrito a seguir:
Grau do vértice a = graus (a) = 2
Grau do vértice b = graus (b) = 2
Grau do vértice c = graus (c) = 2
Grau do vértice d = graus (d) = 2
Grau do vértice e = graus (e) = 0
Neste gráfico, não há vértice pendente e o vértice 'e' é um vértice isolado.
Grau do vértice no gráfico direcionado
Se o gráfico for um gráfico direcionado, então neste gráfico, cada vértice deve ter um grau de entrada e um grau de saída. Suponha que haja um gráfico direcionado. Neste gráfico, podemos usar as seguintes etapas para descobrir o grau de entrada, o grau de saída e o grau de um vértice.
Grau de entrada de um vértice
O grau de entrada de um vértice pode ser descrito como um número de arestas com v, onde v é usado para indicar o vértice terminal. Em outras palavras, podemos descrevê-lo como uma série de arestas que chegam ao vértice. Com a ajuda da sintaxe deg-(v), podemos escrever o grau de entrada de um vértice. Se quisermos determinar o grau de entrada de um vértice, para isso temos que contar o número de arestas que terminam no vértice.
Grau externo de um vértice
O grau externo de um vértice pode ser descrito como um número de arestas com v, onde v é usado para indicar o vértice inicial. Em outras palavras, podemos descrevê-lo como uma série de arestas saindo do vértice. Com a ajuda da sintaxe deg+(v), podemos escrever o grau externo de um vértice. Se quisermos determinar o grau de saída de um vértice, para isso temos que contar o número de arestas que começa no vértice.
Grau de um vértice
O grau de um vértice é indicado com a ajuda de deg(v), que é igual à adição do grau de entrada de um vértice e do grau de saída de um vértice. A representação simbólica do grau de um vértice é descrita a seguir:
Deg(v) = deg-(v) + deg+(v)
Exemplo 1: Neste exemplo, temos um gráfico e temos que determinar o grau de cada vértice.
Solução: Para isso, primeiro descobriremos o grau de um vértice, o grau de entrada de um vértice e depois o grau de saída de um vértice.
Como podemos ver que o gráfico acima contém o total de 6 vértices, ou seja, v1, v2, v3, v4, v5 e v6.
Em grau:
Grau de entrada de um vértice v1 = deg(v1) = 1
Grau de entrada de um vértice v2 = deg(v2) = 1
Grau de entrada de um vértice v3 = deg(v3) = 1
Grau de entrada de um vértice v4 = deg(v4) = 5
Grau de entrada de um vértice v5 = deg(v5) = 1
Grau de entrada de um vértice v6 = deg(v6) = 0
Grau externo:
Grau externo de um vértice v1 = deg(v1) = 2
Grau externo de um vértice v2 = graus (v2) = 3
Grau externo de um vértice v3 = deg(v3) = 2
Grau externo de um vértice v4 = deg(v4) = 0
Grau externo de um vértice v5 = deg(v5) = 2
Grau externo de um vértice v6 = deg(v6) = 0
Grau de um vértice
Com a ajuda da definição descrita acima, sabemos que o grau de um vértice Deg(v) = deg-(v) + você+(v). Agora vamos calculá-lo com a ajuda desta fórmula como esta:
Grau de um vértice v1 = deg(v1) = 1+2 = 3
Grau de um vértice v2 = graus(v2) = 1+3 = 4
Grau de um vértice v3 = graus(v3) = 1+2 = 3
Grau de um vértice v4 = deg(v4) = 5+0 = 5
Grau de um vértice v5 = deg(v5) = 1+2 = 3
Grau de um vértice v6 = deg(v6) = 0+0 = 0
Exemplo 2:
Neste exemplo, temos um gráfico direcionado com 7 vértices. O vértice 'a' contém 2 arestas, ou seja, 'ad' e 'ab', que vão para fora. Conseqüentemente, o vértice 'a' contém o grau externo, que é 2. Da mesma forma, o vértice 'a' também tem uma aresta 'ga', que vem em direção a este vértice 'a'. Portanto, o vértice 'a' contém o grau de entrada, que é 1.
Solução: O grau de entrada e de saída de todos os vértices acima são descritos a seguir:
Em grau:
Grau de entrada de um vértice a = deg(a) = 1
Grau de entrada de um vértice b = graus (b) = 2
Grau de entrada de um vértice c = deg(c) = 2
Grau de entrada de um vértice d = graus (d) = 1
Grau de entrada de um vértice e = grau (e) = 1
Grau de entrada de um vértice f = deg(f) = 1
Grau de entrada de um vértice g = graus (g) = 0
Grau externo:
Grau externo de um vértice a = graus (a) = 2
Grau externo de um vértice b = graus (b) = 0
Grau externo de um vértice c = graus (c) = 1
Grau externo de um vértice d = graus (d) = 1
Grau externo de um vértice e = graus (e) = 1
Grau externo de um vértice f = deg(f) = 1
Grau externo de um vértice g = graus (g) = 2
Grau de cada vértice:
Sabemos que o grau de um vértice Deg(v) = deg-(v) + você+(v). Agora vamos calculá-lo com a ajuda desta fórmula como esta:
Grau de um vértice a = graus (a) = 1+2 = 3
Grau de um vértice b = graus (b) = 2+0 = 2
Grau de um vértice c = graus (c) = 2+1 = 3
Grau de um vértice d = graus (d) = 1+1 = 2
Grau de um vértice e = graus(e) = 1+1 = 2
Grau de um vértice f = graus(f) = 1+1 = 2
Grau de um vértice g = graus (g) = 0+2 = 2
Exemplo 3: Neste exemplo, temos um gráfico direcionado com 5 vértices. O vértice 'a' contém 1 aresta, ou seja, 'ae', que vai para fora. Portanto, o vértice 'a' contém um grau externo, que é 1. Da mesma forma, o vértice 'a' também tem uma aresta 'ba', que vem em direção a este vértice 'a'. Portanto, o vértice 'a' contém o grau de entrada, que é 1.
Solução: O grau de entrada e de saída de todos os vértices acima são descritos a seguir:
Grau
Grau de entrada de um vértice a = deg(a) = 1
Grau de entrada de um vértice b = graus (b) = 0
Grau de entrada de um vértice c = deg(c) = 2
Neena Gupta
Grau de entrada de um vértice d = graus (d) = 1
Grau de entrada de um vértice e = grau (e) = 1
Grau externo:
Grau externo de um vértice a = deg(a) = 1
Grau externo de um vértice b = graus (b) = 2
Grau externo de um vértice c = graus (c) = 0
história em java
Grau externo de um vértice d = graus (d) = 1
Grau externo de um vértice e = graus (e) = 1
Grau de cada vértice:
Sabemos que o grau de um vértice Deg(v) = deg-(v) + você+(v). Agora vamos calculá-lo com a ajuda desta fórmula como esta:
Grau de um vértice a = deg(a) = 1+1 = 2
Grau de um vértice b = graus (b) = 0+2 = 2
Grau de um vértice c = graus (c) = 2+0 = 2
Grau de um vértice d = graus (d) = 1+1 = 2
Grau de um vértice e = graus(e) = 1+1 = 2
Exemplo 4: Neste exemplo, temos um gráfico e temos que determinar o grau, o grau de entrada e o grau de saída de cada vértice.
Solução: Para isso, primeiro descobriremos o grau de entrada de um vértice e depois o grau de saída de um vértice.
Como podemos ver que o gráfico acima contém o total de 8 vértices, ou seja, 0, 1, 2, 3, 4, 5 e 6.
Em grau:
Grau de entrada de um vértice 0 = deg(0) = 1
Grau de entrada de um vértice 1 = deg(1) = 2
Grau de entrada de um vértice 2 = deg(2) = 2
Grau de entrada de um vértice 3 = deg(3) = 2
Grau de entrada de um vértice 4 = deg(4) = 2
Grau de entrada de um vértice 5 = deg(5) = 2
Grau de entrada de um vértice 6 = deg(6) = 2
Grau externo:
Grau externo de um vértice 0 = graus (0) = 2
Grau externo de um vértice 1 = deg(1) = 1
Grau externo de um vértice 2 = graus (2) = 3
Grau externo de um vértice 3 = graus (3) = 2
Grau externo de um vértice 4 = graus (4) = 2
Grau externo de um vértice 5 = graus (5) = 2
Grau externo de um vértice 6 = deg(6) = 1
Grau de cada vértice:
Sabemos que o grau de um vértice Deg(v) = deg-(v) + você+(v). Agora vamos calculá-lo com a ajuda desta fórmula como esta:
Grau de um vértice 0 = graus(0) = 1+2 = 3
Grau de um vértice 1 = grau(1) = 2+1 = 3
Grau de um vértice 2 = graus(2) = 2+3 = 5
Grau de um vértice 3 = graus(3) = 2+2 = 4
Grau de um vértice 4 = graus(4) = 2+2 = 4
Grau de um vértice 5 = graus(5) = 2+2 = 4
Grau de um vértice 6 = graus(5) = 2+1 = 3
Sequência de graus de um gráfico
Para determinar a sequência de graus de um gráfico, precisamos primeiro determinar o grau de cada vértice de um gráfico. Depois disso, escreveremos esses graus em ordem crescente. Esta ordem/sequência pode ser chamada de sequência de graus de um gráfico.
Por exemplo: Neste exemplo, temos três gráficos que possuem 3, 4 e 5 vértices, e a sequência de graus de todos os gráficos é 3.
No gráfico acima, existem 3 vértices. O grau de uma sequência deste gráfico é descrito a seguir:
No gráfico acima, existem 4 vértices. A sequência de graus deste gráfico é descrita a seguir:
No gráfico acima, existem 5 vértices. A sequência de graus deste gráfico é descrita a seguir: