O gráfico consiste em vértices e arestas. Os vértices são conectados por arestas de acordo com uma certa propriedade - a relação de incidência, que define o conjunto de arestas. Nesse caso, loops e vértices isolados podem se formar.
Instruções
Passo 1
Deixe o conjunto de arestas do gráfico ser dado e a relação ao longo da qual é possível desenhar uma aresta de um vértice para outro é dada. Como exemplo, o conjunto de vértices {1, 2, 3, 4, 5, 6, 7, 8}, dois vértices x e y estão na proporção x + y <8.
Passo 2
Construa uma matriz de adjacência de vértices. Para fazer isso, construa uma tabela quadrada, o número de linhas e colunas da tabela coincide com o número de vértices. Em seguida, coloque 1 na intersecção da i-ésima linha e j-ésima coluna se os vértices i e j satisfizerem a proporção dada. Coloque 0 na interseção da i-ésima linha e j-ésima coluna se a proporção para os elementos correspondentes não for atendida.
Em nosso exemplo, a primeira linha é preenchida da seguinte maneira:
1 + 1 <8, então há 1 na interseção da 1ª linha e 1ª coluna
1 + 2 <8, novamente 1
1 + 3 <8, novamente 1
1 + 7 <8, desigualdade incorreta, então este elemento da tabela será 0
1 + 8 <8, novamente 0
etapa 3
Para descobrir o número de arestas, conte o número de unidades na matriz de adjacência sem duplicar as arestas.
No exemplo, uma matriz simétrica foi obtida, então contamos primeiro os que estão acima da diagonal principal da matriz (marcados em azul), e depois os que estão na diagonal principal (marcados em vermelho). O número total de costelas é 12.
Passo 4
Construa uma matriz de incidentes (bordas). Para fazer isso, desenhe uma tabela, o número de linhas nela é igual ao número de vértices no gráfico e o número de colunas é igual ao número de arestas. Coloque unidades nessas linhas que serão conectadas por uma aresta. As arestas que vão do vértice a ele são chamadas de loops e são adicionadas ao final da matriz. Nas colunas correspondentes aos loops, existe apenas uma unidade, em contraste com as demais arestas.
Etapa 5
Agora desenhe um gráfico. Coloque os vértices no papel de qualquer maneira e conecte-os com as bordas usando as tabelas construídas. Os vértices que não são conectados por arestas são chamados de isolados.
