PALESTRA Nº 10. Contagens

1. O conceito de gráfico. Formas de representar um gráfico

Um grafo é um par G = (V,E), onde V é um conjunto de objetos de natureza arbitrária, chamados vértices, e E é uma família de pares ei = (vil, vi2), vijOV, chamados arestas. No caso geral, o conjunto V e/ou a família E podem conter um número infinito de elementos, mas consideraremos apenas grafos finitos, ou seja, grafos para os quais V e E são finitos. Se a ordem dos elementos incluídos em ei importa, então o gráfico é chamado direcionado, abreviado - dígrafo, caso contrário - não direcionado. As arestas de um dígrafo são chamadas de arcos. No que segue, assumimos que o termo "grafo", usado sem especificação (direcionado ou não direcionado), denota um grafo não direcionado.

Se e = , então os vértices v e u são chamados de extremidades da aresta. Aqui dizemos que a aresta e é adjacente (incidente) a cada um dos vértices v e u. Os vértices v e e também são chamados de adjacentes (incidentes). No caso geral, arestas da forma e = ; tais arestas são chamadas de laços.

O grau de um vértice em um grafo é o número de arestas incidentes nesse vértice, com os loops sendo contados duas vezes. Como cada aresta é incidente a dois vértices, a soma dos graus de todos os vértices no gráfico é igual ao dobro do número de arestas: Sum(deg(vi), i=1...|V|) = 2 * | E|.

O peso de um nó é um número (real, inteiro ou racional) atribuído a um determinado nó (interpretado como custo, rendimento, etc.). Peso, comprimento da borda - um número ou vários números que são interpretados como comprimento, largura de banda, etc.

Um caminho em um grafo (ou uma rota em um dígrafo) é uma sequência alternada de vértices e arestas (ou arcos em um dígrafo) da forma v0, (v0,v1), v1..., (vn - 1,vn ), v. O número n é chamado de comprimento do caminho. Um caminho sem arestas repetidas é chamado de cadeia; um caminho sem vértices repetidos é chamado de cadeia simples. O caminho pode ser fechado (v0 = vn). Um caminho fechado sem arestas repetidas é chamado de ciclo (ou contorno em um dígrafo); sem repetir vértices (exceto o primeiro e o último) - um loop simples.

Um grafo é dito conectado se houver um caminho entre quaisquer dois de seus vértices, e desconectado caso contrário. Um grafo desconectado consiste em vários componentes conectados (subgrafos conectados).

Existem várias maneiras de representar gráficos. Vamos considerar cada um deles separadamente.

1. Matriz de incidência.

Esta é uma matriz retangular de dimensão nx n, onde n é o número de vértices, am é o número de arestas. Os valores dos elementos da matriz são determinados da seguinte forma: se a aresta xi e o vértice vj são incidentes, então o valor do elemento da matriz correspondente é igual a um, caso contrário o valor é zero. Para grafos direcionados, a matriz de incidência é construída de acordo com o seguinte princípio: o valor do elemento é igual a -1 se a aresta xi vier do vértice vj, igual a 1 se a aresta xi entrar no vértice vj, e igual a XNUMX caso contrário .

2. Matriz de adjacência.

Esta é uma matriz quadrada de dimensão nxn, onde n é o número de vértices. Se os vértices vi e vj são adjacentes, ou seja, se existe uma aresta conectando-os, então o elemento da matriz correspondente é igual a um, caso contrário é igual a zero. As regras para construir esta matriz para gráficos direcionados e não direcionados não são diferentes. A matriz de adjacência é mais compacta que a matriz de incidência. Deve-se notar que esta matriz também é muito esparsa, mas no caso de um gráfico não direcionado ela é simétrica em relação à diagonal principal, portanto você pode armazenar não a matriz inteira, mas apenas metade dela (uma matriz triangular ).

3. Lista de adjacências (incidentes).

É uma estrutura de dados que armazena uma lista de vértices adjacentes para cada vértice do grafo. A lista é uma matriz de ponteiros, cujo i-ésimo elemento contém um ponteiro para a lista de vértices adjacentes ao i-ésimo vértice.

Uma lista de adjacências é mais eficiente que uma matriz de adjacências porque elimina o armazenamento de elementos nulos.

4. Lista de listas.

É uma estrutura de dados em forma de árvore na qual um ramo contém listas de vértices adjacentes a cada um dos vértices do grafo, e o segundo ramo aponta para o próximo vértice do grafo. Essa maneira de representar o gráfico é a mais ideal.

2. Representação de um gráfico por uma lista de incidências. Algoritmo de Percurso de Profundidade do Gráfico

Para implementar um gráfico como uma lista de incidência, você pode usar o seguinte tipo:

TipoLista = ^S;

end;

Então o gráfico é definido da seguinte forma:

Var Gr : array[1..n] de Lista;

Agora vamos nos voltar para o procedimento de travessia do gráfico. Este é um algoritmo auxiliar que permite visualizar todos os vértices do gráfico, analisar todos os campos de informação. Se considerarmos uma travessia de grafos em profundidade, existem dois tipos de algoritmos: recursivos e não recursivos.

Com o algoritmo de travessia recursiva em profundidade, tomamos um vértice arbitrário e encontramos um vértice invisível (novo) v adjacente a ele. Então tomamos o vértice v como não novo e encontramos qualquer novo vértice adjacente a ele. Se algum vértice não tiver vértices não vistos mais recentes, consideramos esse vértice como usado e retornamos um nível acima do vértice de onde chegamos ao vértice usado. A travessia continua dessa maneira até que não haja novos vértices não varridos no grafo.

Em Pascal, a travessia em profundidade ficaria assim:

Procedimento Obhod(gr : Gráfico; k : Byte);

End;

Nota

Neste procedimento, ao descrever o tipo Graph, nos referimos à descrição de um gráfico por uma lista de listas. Array nov[i] é um array especial cujo i-ésimo elemento é True se o i-ésimo vértice não for visitado, e False caso contrário.

Um algoritmo de travessia não recursivo também é frequentemente usado. Nesse caso, a recursão é substituída por uma pilha. Depois que um vértice é visualizado, ele é colocado na pilha e é usado quando não há mais novos vértices adjacentes a ele.

3. Representação de um gráfico por uma lista de listas. Algoritmo de Percurso de Largura

Um gráfico pode ser definido usando uma lista de listas da seguinte forma:

TipoLista = ^Tlista;

end;

Ao percorrer o grafo em largura, selecionamos um vértice arbitrário e examinamos todos os vértices adjacentes a ele de uma só vez. Uma fila é usada em vez de uma pilha. O algoritmo de busca em largura é muito útil para encontrar o caminho mais curto em um grafo.

Aqui está um procedimento para percorrer um gráfico em largura em pseudocódigo:

Procedimento Obhod2(v);

End;

Autor: Tsvetkova A.V.

<< Voltar: Contagens (O conceito de gráfico. Métodos de representação de um gráfico. Representação de um gráfico por uma lista de incidências. Algoritmo de travessia em profundidade para um gráfico. Representação de um gráfico como uma lista de listas. Algoritmo de travessia em largura para um gráfico )

>> Encaminhar: Métodos (Métodos. Construtores e destruidores. Destruidores. Métodos virtuais. Campos de dados de objetos e parâmetros de métodos formais)

Recomendamos artigos interessantes seção Notas de aula, folhas de dicas:

▪ Ciência de materiais. Notas de aula

▪ Traumatologia e ortopedia. Notas de aula

▪ Administração estadual e municipal. Berço

Veja outros artigos seção Notas de aula, folhas de dicas.

Leia e escreva útil comentários sobre este artigo.

<< Voltar

Últimas notícias de ciência e tecnologia, nova eletrônica:

A existência de uma regra de entropia para o emaranhamento quântico foi comprovada 09.05.2024

A mecânica quântica continua a nos surpreender com seus fenômenos misteriosos e descobertas inesperadas. Recentemente, Bartosz Regula do Centro RIKEN de Computação Quântica e Ludovico Lamy da Universidade de Amsterdã apresentaram uma nova descoberta que diz respeito ao emaranhamento quântico e sua relação com a entropia. O emaranhamento quântico desempenha um papel importante na moderna ciência e tecnologia da informação quântica. No entanto, a complexidade da sua estrutura torna a sua compreensão e gestão um desafio. A descoberta de Regulus e Lamy mostra que o emaranhamento quântico segue uma regra de entropia semelhante à dos sistemas clássicos. Esta descoberta abre novas perspectivas na ciência e tecnologia da informação quântica, aprofundando a nossa compreensão do emaranhamento quântico e a sua ligação à termodinâmica. Os resultados do estudo indicam a possibilidade de reversibilidade das transformações de emaranhamento, o que poderia simplificar muito seu uso em diversas tecnologias quânticas. Abrindo uma nova regra ... >>

Mini ar condicionado Sony Reon Pocket 5 09.05.2024

O verão é uma época de relaxamento e viagens, mas muitas vezes o calor pode transformar essa época em um tormento insuportável. Conheça um novo produto da Sony – o minicondicionador Reon Pocket 5, que promete deixar o verão mais confortável para seus usuários. A Sony lançou um dispositivo exclusivo - o minicondicionador Reon Pocket 5, que fornece resfriamento corporal em dias quentes. Com ele, os usuários podem desfrutar do frescor a qualquer hora e em qualquer lugar, simplesmente usando-o no pescoço. Este miniar condicionado está equipado com ajuste automático dos modos de operação, além de sensores de temperatura e umidade. Graças a tecnologias inovadoras, o Reon Pocket 5 ajusta o seu funcionamento em função da atividade do utilizador e das condições ambientais. Os usuários podem ajustar facilmente a temperatura usando um aplicativo móvel dedicado conectado via Bluetooth. Além disso, camisetas e shorts especialmente desenhados estão disponíveis para maior comodidade, aos quais um mini ar condicionado pode ser acoplado. O dispositivo pode, oh ... >>

Energia do espaço para Starship 08.05.2024

A produção de energia solar no espaço está se tornando mais viável com o advento de novas tecnologias e o desenvolvimento de programas espaciais. O chefe da startup Virtus Solis compartilhou sua visão de usar a Starship da SpaceX para criar usinas orbitais capazes de abastecer a Terra. A startup Virtus Solis revelou um ambicioso projeto para criar usinas de energia orbitais usando a Starship da SpaceX. Esta ideia poderia mudar significativamente o campo da produção de energia solar, tornando-a mais acessível e barata. O cerne do plano da startup é reduzir o custo de lançamento de satélites ao espaço usando a Starship. Espera-se que este avanço tecnológico torne a produção de energia solar no espaço mais competitiva com as fontes de energia tradicionais. A Virtual Solis planeja construir grandes painéis fotovoltaicos em órbita, usando a Starship para entregar os equipamentos necessários. Contudo, um dos principais desafios ... >>

Notícias aleatórias do Arquivo Trem de alta velocidade na Coreia 05.02.2005 Desde março de 2004, a primeira linha ferroviária de alta velocidade está operando na República da Coreia. Ela conectou Seul com Busan. A tecnologia francesa é usada, mas as composições são feitas principalmente na Coréia. A extensão da linha é de 412 quilômetros, dos quais 190 quilômetros são túneis e 120 quilômetros são pontes e viadutos. O trem funciona desta forma em 2 horas e 40 minutos.

Outras notícias interessantes:

▪ Amplificador acústico eficiente em miniatura

▪ Descarte de amianto

▪ Receptor Yamaha RX-N600

▪ A reação a um cigarro depende das ideias sobre sua composição.

▪ Scanner de alimentos domésticos

Feed de notícias de ciência e tecnologia, nova eletrônica

Materiais interessantes da Biblioteca Técnica Gratuita:

▪ seção do site Para quem gosta de viajar - dicas para turistas. Seleção de artigos

▪ artigo Sonho de cristal da minha infância. expressão popular

▪ artigo Qual ave detém o recorde de profundidade de mergulho? Resposta detalhada

▪ artigo Vice-Diretor Geral. Descrição do trabalho

▪ artigo Batendo detector de metais com gatilho Schmidt. Enciclopédia de rádio eletrônica e engenharia elétrica

▪ artigo Mensagem oculta. Segredo do foco

Deixe seu comentário neste artigo:

Todos os idiomas desta página

Arabic	Hebrew	Polish
Bengali	Hindi	Portuguese
Chinese	Italian	Spanish
English	Japanese	Turkish
French	Korean	Ukrainian
German	Malay	Vietnamese

Página principal | Biblioteca | Artigos | Mapa do Site | Revisões do site

www.diagrama.com.ua
2000-2024