Artigos

5: Teoria dos grafos


Este mapa de texto ainda está em construção. Por favor, nos perdoe.


O que é um gráfico K5?

Definição. Um bipartido completo gráfico é um gráfico cujos vértices podem ser particionados em dois subconjuntos V1 e V2 de modo que nenhuma aresta tenha ambos os pontos de extremidade no mesmo subconjunto, e cada aresta possível que poderia conectar vértices em subconjuntos diferentes faz parte do gráfico.

Também se pode perguntar: o que é um gráfico k4? Uma completa gráfico é um gráfico em que cada par de gráfico vértices são conectados por uma aresta. O completo gráfico com gráfico vértices é denotado e tem (os números triangulares) arestas não direcionadas, onde. é um coeficiente binomial. Na literatura mais antiga, complete gráficos às vezes são chamados de universais gráficos.

Além disso, k5 é planar?

K5: K5 tem 5 vértices e 10 arestas, e assim pelo Lema 2 não é planar. K3,3: K3,3 tem 6 vértices e 9 arestas, e por isso não podemos aplicar o Lema 2. Mas observe que ele é bipartido e, portanto, não tem ciclos de comprimento 3. Na verdade, qualquer gráfico que contenha um & ld incorporação cotopológica & rdquo de um gráfico não planar é não planar.


Introdução da Teoria dos Grafos

No primeiro semestre de 2005, fiz o curso de matemática chamado & quot Teoria Gráfica (MATH6690). & Quot Este curso é difícil, mas muito interessante e abre meus olhos para um novo mundo matemático.

Eu adoro estudar a teoria dos grafos e realmente quero que você estude essa matemática muito jovem.

Este campo da matemática pode ser aplicado a muitas questões, variando da pesquisa operacional e química à genética e linguística, e da engenharia elétrica e geografia à sociologia e arquitetura.

O que é a teoria dos grafos?

A teoria dos grafos diz respeito à relação entre linhas e pontos.

Um gráfico consiste em alguns pontos e algumas linhas entre eles.

Nenhuma atenção é dada à posição dos pontos e ao comprimento das linhas.

Assim, os dois gráficos abaixo são o mesmo gráfico.

Você pode obter informações mais detalhadas sobre a teoria dos grafos neste site (http://www.netipedia.com/index.php/Graph_theory)

Termos básicos da teoria dos grafos

uma SIMPLESo gráfico G é aquele que satisfaz que

(1) tendo no máximo uma aresta (linha) entre quaisquer dois vértices (pontos) e,

(2) não ter uma aresta voltando ao vértice original.

Mostro dois exemplos de gráficos que não são simples.

Exemplo: Este gráfico não é simples porque possui uma aresta que não satisfaz (2). A borda é um laço.

Exemplo: Este gráfico não é simples porque possui 2 arestas entre os vértices A e B.

Dois vértices, v e w, de um gráfico são ADJACENTEse houver uma aresta, vx, unindo-os, os vértices são então considerados INCIDENTE para a borda, vx.

O GRAU de um vértice v de um gráfico é o número de arestas incidentes com v.

Exemplo: O grau de cada vértice no gráfico abaixo é representado pelo número.

Definições exatas na página da web, Math World

Gráfico simples (http://mathworld.wolfram.com/SimpleGraph.html)

Grau do vértice (http://mathworld.wolfram.com/VertexDegree.html)

Encontre todos os seis gráficos simples com 4 vértices.

Encontre o dgree de cada vértice do gráfico abaixo.

Algumas questões interessantes na teoria dos grafos.

Eu mostro três questões na Teoria dos Grafos que são interessantes e básicas.

1. Lema do aperto de mão (devido essencialmente a Leonhard Euler em 1736)

Se várias pessoas apertam as mãos, qual é o número total de mãos apertadas?

(Observe que não é o número de apertos de mão.)

Quando usamos alguns termos da teoria dos grafos para pensar nessa questão, podemos considerar um vértice e uma aresta como uma pessoa e um aperto de mão, respectivamente.

Como uma aresta incide com 2 vértices (observe que G é simples), podemos ver facilmente que 1 aperto de mão consiste em 2 pessoas, ou seja, 2 mãos.

Segue-se que o número total de mãos agitadas é o dobro do número de mãos dadas.

Infelizmente, não podemos dizer o número exato de apertos de mão porque não sabemos o número de apertos de mão.

Tudo o que sabemos é que o número de mãos apertadas é par.

Em termos de teoria dos grafos, em qualquer gráfico, a soma de todos os graus dos vértices é um número par - na verdade, duas vezes o número de arestas.

Além disso, podemos dizer que em qualquer gráfico o número de vértices de grau ímpar é par.

Considere um problema típico de perguntar se um dado diagrama pode ser desenhado sem tirar o lápis do papel e sem repetir nenhuma linha (: desenhar uma imagem com um único traço).

Problema: Qual dos gráficos 1, 2 e 3 abaixo pode ser desenhado com um único traço?

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Os gráficos 1 e 2 podem ser desenhados da maneira desejada, mas o gráfico 3 não.

Você viu a diferença entre a forma de desenhar o gráfico 1 e a do gráfico 2?

Com relação aos desenhos de um traço do gráfico 1, o ponto final é igual ao ponto inicial. Em contraste, os desenhos de um traço do gráfico 2 têm um início e um final diferentes.

Como o gráfico 1 acima, se um gráfico tem uma maneira de ir de um vértice a outro que inclui cada aresta exatamente uma vez e termina no vértice inicial, então o gráfico é Euleriana (é um gráfico Euleriano).

Como o gráfico 2 acima, se um gráfico tem maneiras de ir de um vértice a outro que incluem todas as arestas exatamente uma vez e termina em outro vértice diferente do inicial, então o gráfico é semi-Euleriano (é um gráfico semi-Euleriano).

O nome 'Eulerian' surge do fato de que o matemático Euler foi a primeira pessoa a resolver o famoso problema & quotK & oumlnigsberg bridges problem & quot, que informa como cruzar cada uma das sete pontes na Figura abaixo exatamente uma vez e retornar ao seu ponto de atordoamento.

Isso equivale a perguntar se o gráfico abaixo possui uma trilha Euleriana, ou seja, se o gráfico é Euleriano.

Exercício: tente encontrar uma trilha Euleriana no gráfico de Koumlnigsberg.

Acho que você não conseguiu encontrar nenhuma trilha de Euler porque Euler provou matematicamente que ninguém consegue encontrar qualquer desenho de um traço naquele gráfico.

Aqui está o teorema mais famoso e simples (Euler 1736) sobre se um dado gráfico é euleriano ou não.

Um grafo conectado G é Euleriano se e somente se o grau de cada vértice de G é par

Por este teorema, o gráfico do problema das pontes de Koumlnigsberg é insolúvel.

Embora tenhamos considerado na seção & quotEulerian graph & quot uma maneira de ir e voltar incluindo todas as arestas de um gráfico, consideramos aqui um problema semelhante de circular em um gráfico incluindo cada & quotvertex & quot (não & quotedge & quot).

Problema: Qual dos gráficos 1, 2 e 3 abaixo tem uma maneira de passar todos os vértices?

aaaaaaaaaaaaaaaaaaa

O gráfico 1 e o gráfico 2 possuem tal forma (conforme mostrado abaixo), mas o gráfico 3 não.

Semelhante à história do gráfico Euleriano, há uma diferença entre a forma do gráfico 1 e o gráfico 2. Trata-se dos pontos finais dos caminhos.

No que diz respeito ao caminho do gráfico 1, o ponto final é igual ao ponto inicial. Em contraste, o caminho do gráfico 2 tem um início e um fim diferentes.

Como o gráfico 1 acima, se um gráfico tem um caminho que inclui cada vértice exatamente uma vez, enquanto termina no vértice inicial, o gráfico é hamiltoniano (é um gráfico hamiltoniano). Esse caminho é chamado de & quotCiclo de Hamiltoniano & quot.

Como o gráfico 2 acima, se um gráfico tem um caminho que inclui cada vértice exatamente uma vez, mas terminando em outro vértice que não o inicial, então o gráfico é semi-hamiltoniano (é um gráfico semi-hamiltoniano).

Lembre-se de que na seção anterior de & quot Euleriano & quot, vimos o teorema muito simples e útil sobre dizer se um gráfico é euleriano ou não. Porque, infelizmente, pouco se sabe em geral sobre o ciclo hamiltoniano, a descoberta de tal caracterização é um dos problemas não resolvidos da teoria dos grafos.

Encontre um ciclo hamiltoniano do gráfico abaixo.

Encontre um ciclo hamiltoniano do gráfico abaixo.

(Este problema é bastante difícil. No entanto, isso não significa que não haja resposta.)

Eu introduzi algumas terminologias e conceitos básicos da teoria dos grafos.

Quase acabo minha explicação para a introdução da teoria dos grafos.

Mas tenho muitos outros assuntos interessantes que gostaria de mostrar.

Aqui, apenas faço uma lista dessas questões com hiperlinks para sua definição e explicação.

Algumas das questões têm forte conexão com outras áreas de estudo.

Vá em frente e leia para estudar a Teoria dos Grafos. Referi-me à explicação deste livro para fazer este ensaio.


B8.5 Teoria dos Grafos (2016-2017)

Os gráficos (redes abstratas) estão entre as estruturas matemáticas mais simples, mas, apesar disso, possuem uma teoria estrutural muito rica e bem desenvolvida. Uma vez que os gráficos surgem naturalmente em muitos contextos dentro e fora da matemática, a Teoria dos Grafos é uma área importante da matemática e também tem muitas aplicações em outros campos, como a ciência da computação.

O objetivo principal da unidade curricular é apresentar as ideias fundamentais da Teoria dos Grafos e algumas das técnicas básicas da combinatória.

O aluno terá desenvolvido uma compreensão básica das propriedades dos gráficos e uma apreciação dos métodos combinatórios usados ​​para analisar estruturas discretas.

Introdução: definições básicas e exemplos. Árvores e sua caracterização. Euler circunda caminhos e ciclos longos. Colorações de vértices: teorema de Brooks, polinômio cromático. Coloração das bordas: teorema de Vizing. Gráficos planos, incluindo fórmula de Euler, gráficos duais. Fluxo máximo - teorema do corte mínimo: aplicações incluindo o teorema de Menger e o teorema de Hall. Teorema de Tutte sobre as correspondências. Problemas extremos: teorema de Turan, problema de Zarankiewicz, teorema de Erd & # 337s-Stone.

Observe que as versões e-book de muitos livros nas listas de leitura podem ser encontradas em SOLO e ORLO.


Teoria dos Grafos

Este livro padrão da teoria dos grafos moderna, agora em sua quinta edição, combina a autoridade de um clássico com o frescor envolvente do estilo que é a marca registrada da matemática ativa. Ele cobre o material central do assunto com provas concisas, mas confiáveis, completas, enquanto oferece vislumbres de métodos mais avançados em cada campo por um ou dois resultados mais profundos, novamente com provas fornecidas em todos os detalhes.

O livro pode ser usado como um texto confiável para um curso introdutório, como um texto de pós-graduação e para auto-estudo.

“Este livro excepcional não pode ser substituído por nenhum outro livro no mercado atual de livros didáticos. Ele tem todas as chances de se tornar o livro-texto padrão para a teoria dos grafos. ” Acta Scientiarum Mathematiciarum

“Profundo, claro, maravilhoso. Este é um livro sério sobre o coração da teoria dos grafos. Tem

profundidade e integridade. ” Persi Diaconis e Ron Graham, SIAM Review

“O livro teve uma recepção muito entusiástica, que muito merece. Uma elucidação magistral da moderna teoria dos grafos. ”

Boletim do Instituto de Combinatória e suas Aplicações

“O sucesso é espetacular. um livro muito bom. ” Comentários MAA

“Um destaque do livro é o que é, de longe, o melhor relato impresso da teoria de gráficos menores de Seymour-Robertson.” Mathematika

“. como ouvir alguém explicar matemática. ” Boletim da AMS


Introdução à Teoria dos Grafos - Segunda edição

Em uma página separada está uma discussão sobre a notação para o número de vértices e o número de arestas de um gráfico G, com base no feedback da comunidade de matemática discreta.

Comentários sobre outros aspectos da terminologia também são bem-vindos. No entanto, não espero fazer nenhuma mudança em relação a "ciclo" vs. "circuito". "Gráfico par" é a minha expressão de compromisso para a condição de que todos os graus do vértice sejam pares e continuarei a usar "ciclo" para um gráfico conectado 2-regular, "circuito" para um gráfico par conectado com ordem cíclica de aresta e "circuito" para um conjunto dependente mínimo em uma matróide.

Totais de votos
Questão 1: "gráfico simples" / "gráfico" - 17.5 "gráfico" / "multigrafo" - 53 "gráfico simples" / "gráfico" / "multigrafo" - 4 outro - 2.
Questão 2: "conjuntos partidários" - 21 "classes de cores" - 14.5 "partes" - 9 "classes" ou "classes de vértices" - 3 "lados" - 5 "blocos" - .5 "costas" - 2 "classes bipartidas" - 1.
Pergunta 3: "caminhos separados internamente aos pares" - 13 "caminhos independentes" - 31 outro - 6 ("internamente independente", "vértice-disjunta", etc.).
Questão 4: "M-saturado" - 11 "M-abordado" - 20.5 outro - 2 ("coincide").
Questão 5: " chi (Gk)" - 0 " piG(k)" - 0 "PG(k)" - 1 outro - 0.

Questão 1: gráfico, gráfico simples, multigrafo

Esta escolha pode não ser a melhor. A maioria das pesquisas e aplicações da teoria dos grafos diz respeito a grafos sem arestas ou loops múltiplos, e muitas vezes arestas múltiplas podem ser modeladas por pesos de aresta. Por outro lado, alguns tópicos naturalmente usam bordas múltiplas (circuitos Eulerianos 1.2, enumeração de árvore de abrangência 2.2, correspondência bipartida 3.1, conectividade de borda 4.1, fluxo de rede 4.3, orientações acíclicas 5.3, embeddings e seus duais 6.1-6.3, coloração de borda 7.1 , matróides e menores 8.2). Outros tópicos excluem ou ignoram arestas múltiplas (independência e dominação 3.1, conectividade 4.1, coloração de vértices 5.1-5.3, gráficos livres de triângulos máximos 5.2, gráficos planares máximos e triangulações 6.1, ciclos abrangentes 7.2). É conveniente em pesquisa usar "gráfico" para qualquer modelo que seja o contexto atual, mas essa prática não funciona bem em um curso inicial.

Se a teoria dos grafos não puder decidir isso, considere a matemática de forma mais geral. "Gráfico / multigrafo" seria consistente com "conjunto / multiset" em combinatória. Além disso, "hipergrafo" geralmente se refere a uma família de conjuntos, sem conjuntos repetidos. Por fim, o "gráfico de uma relação" é um subconjunto de um produto cartesiano, sem elementos repetidos. Consistência em matemática sugere o uso de "gráfico / multigrafo".

Existem também considerações pedagógicas. Permitir que o "gráfico" proíba loops e arestas múltiplas simplifica a primeira noção para os alunos, tornando possível visualizar corretamente o conjunto de arestas como um conjunto de pares de vértices e evitar os detalhes técnicos de uma relação de incidência na primeira definição. Alunos iniciantes não precisam saber quais afirmações elementares se estendem sem mudança para multigrafos, instâncias importantes como a fórmula da soma dos graus podem ser mencionadas explicitamente. Quando "gráfico" proíbe loops e arestas múltiplas, usar a palavra "gráfico" pode tornar uma afirmação menos geral, mas não a tornará incorreta. Por outro lado, aprendi por meio de exemplos dolorosos que, quando "gráfico" permite loops e arestas múltiplas, existem incontáveis ​​exercícios que adquirem contra-exemplos irritantes quando a palavra "simples" é omitida.

Questão 2: conjuntos partidários

Em combinatória, os elementos de uma partição são freqüentemente chamados de "blocos", mas essa palavra não está disponível na teoria dos grafos. Outro termo comum é "classes", mas isso parece muito geral. Os teóricos de grafos costumam usar "partes", mas isso parece muito vago e informal para um texto. "Classes de cores" concorda com o uso posterior na coloração, sugere uma escolha da bipartição quando o gráfico é desconectado e se estende a gráficos multipartidos. Infelizmente, "classes de cores" sugere o resultado de um problema de otimização, enquanto uma bipartição é freqüentemente uma condição estrutural pressuposta.

Os termos precisos são estranhos, enquanto os termos usados ​​ao discutir pesquisas parecem muito informais para serem instruídos. Alguém deve ter um bom termo para isso.


ATRIBUIÇÃO 5 TEORIA DO GRÁFICO

Ali e Mannan estão procrastinando em vez de trabalhar em seu projeto.

Mannan encontrou uma peça intitulada "Seis Graus de Separação" escrita por

O dramaturgo norte-americano John Guare que diz que todas as pessoas no mundo são

conectado a todas as outras pessoas do mundo por uma cadeia de no máximo seis

conexões. Mannan afirma que Ali definitivamente conhece Donald Trump por muito menos

de 6 conexões, enquanto Ali diz que mesmo se isso for verdade, Mannan estará relacionado

a Donald Trump por conexões menores do que ele. As coisas aumentam e agora eles

deseja desesperadamente provar seus pontos. Hadi, que está sentado perto, diz que

este problema pode ser facilmente resolvido usando a teoria dos grafos. Ali e Mannan rapidamente

colocar suas habilidades no Google em uso e encontrar um subconjunto de conjuntos de dados de conexões

tornado público por uma popular empresa de mídia social. Mas, uma vez que eles não pagaram

atenção durante suas aulas de Estruturas de Dados, eles não sabem como fazer

deduções úteis do conjunto de dados. Eles precisam de sua ajuda para resolver a disputa

O conjunto de dados mencionado é fornecido a você na forma de um arquivo de texto, ‘amigos.txt’.

Você pode explorar o conjunto de dados fornecido a você, linhas após a primeira linha contém

nomes de pessoas. Você usará a classe de nó para representar uma pessoa. Linhas seguindo o

Conexões de linha é a conexão entre pessoas. Você usará a classe de borda para

representam uma conexão entre duas pessoas.

Você deve analisar o conjunto de dados de duas formas:

1) Se a variável booleana isUnitLenght estiver ligada, todas as arestas devem ter peso igual a

2) Se estiver desligado, você deve escolher o valor fornecido a cada conexão.

Esse valor é chamado de índice de amizade. É medido por quanto

as pessoas interagem umas com as outras. Menor esse valor é para duas pessoas,

mais perto essas pessoas estão umas das outras.

Antes de encontrar a rota entre duas pessoas, você deve verificar se essas duas pessoas

estão até mesmo conectados uns aos outros de acordo com nosso conjunto de dados. Você estudou dois

Algoritmos de acessibilidade, nomeadamente BFS (amplitude primeira pesquisa) e DFS (profundidade primeiro

procurar). Você pode implementar qualquer um deles, mas terá que fornecer um motivo

por que você seguiu com o algoritmo escolhido. Seu algoritmo receberá o nome do primeiro

pessoa (ou seja, seu nó inicial) e para encontrar pessoa (pessoa que você está testando

alcançabilidade para) como entrada e deve retornar verdadeiro se essas duas pessoas estiverem conectadas

Parte 3: Algoritmo do caminho mais curto:

Você estudou o conhecido algoritmo de Dijkstra para o caminho mais curto da classe.

Você implementará o algoritmo de Dijkstra nesta parte para encontrar o caminho mais curto entre

duas pessoas. Terá o nome da pessoa inicial, última pessoa como entrada e irá

retornar um vetor contendo os nomes de todas as pessoas ao longo do caminho. O adicional

a variável d é para o comprimento do caminho.

Para encontrar o caminho mais curto, uma abordagem pode ser encontrar todos os caminhos possíveis

e então procure o mais curto entre eles. Mas, este algoritmo não é escalável e

têm um tempo de execução exponencial. Então, avançamos em direção a um algoritmo mais inteligente

chamado Algoritmo de Dijkstra em homenagem a seu criador Edsgar Dijkstra.

A ideia é manter uma fila de todos os caminhos construídos até o momento, priorizados em termos de

distância (um uso perfeito para a fila de prioridade). Em cada fase, você retira a

o caminho mais curto se leva ao destino, seu trabalho está feito. Caso contrário, você usa

esse caminho como base para a construção de novos caminhos estendidos que adicionam uma borda

levando para longe do nó no final do caminho. Você descarta o estendido

caminho se você já conhece uma maneira melhor de chegar lá (ou seja, você já encontrou um

caminho mais curto para esse nó), caso contrário, você enfileira o caminho estendido para ser

considerado com os outros. Depois de atualizar a fila, você retira a próxima

caminho mais curto e explore a partir daí. A cada etapa, a pesquisa se expande para fora

até encontrar um caminho que termina no destino. Os gráficos nos arquivos de dados são

totalmente conectado, ou seja, cada par de nós é conectado por algum caminho, e

assim, você acabará encontrando um caminho. A ordem dos caminhos considerados pelo

algoritmo garante que você encontrará o caminho mais curto primeiro.

Parte 4: Árvore de abrangência mínima:

MST encontra as arestas no gráfico com peso cumulativo mínimo que conecta o

gráfico inteiro junto. Os MSTs têm uma variedade de aplicações, como minimizar

custo de alguma operação, encontrando clusters em gráficos, encontrando gargalos em gráficos

etc. Você usará o algoritmo de Kruskal para encontrar a árvore de abrangência mínima nesta parte.

Esta função não recebe nenhuma entrada e retorna um vetor de nós, onde cada nó irá

têm apenas as arestas correspondentes ao MST.

Joseph Kruskal desenvolveu um dos algoritmos MST mais simples em 1956. É

com base na ideia de que você considera as arestas no gráfico em ordem crescente

custo. Se os nós nas extremidades da borda estiverem desconectados, você

inclua essa aresta como parte da árvore de abrangência. Se, no entanto, algum caminho já

conecta os nós, você pode descartar essa borda.

A seguir está uma cartilha que o ajudará a começar:

 A parte complicada deste algoritmo é determinar se uma determinada aresta

Deveria ser incluído. A estratégia que você usará é baseada no rastreamento

 Inicialmente, cada nó está em seu próprio conjunto sozinho. O que significa que haverá

“N” conjuntos compostos por nós individuais. Cada conjunto contém os nós,

que são conectados por alguma borda.

 O algoritmo então considera cada aresta, e, por sua vez, ordenada aumentando

peso. (Use getMin () da fila de prioridade para isso)

 Se uma aresta e conecta dois conjuntos diferentes, então e é adicionado ao conjunto de

bordas da árvore geradora mínima, e os dois conjuntos de nós que são

agora conectados por e são mesclados em um único conjunto.

 Se, por outro lado, e conecta dois vértices / nós que já são um

caminho entre eles usando alguma aresta anterior, então e é descartado. (Verificar

para ver se os dois pontos finais da aresta e pertencem ao mesmo conjunto)

 Uma vez que o algoritmo tenha adicionado arestas suficientes para formar uma árvore geradora

(o que significa que apenas um conjunto de nós permanece e esse conjunto contém todos os

nós), ele termina e produz esta árvore como a árvore de abrangência mínima.

Parte 5: Bônus e # 8211 Outro Algoritmo MST:

Esta parte é um bônus. Você usará outro algoritmo para construir um MST.

Este algoritmo é denominado Algoritmo Prims.

Prim & # 8217s é um algoritmo ganancioso que funciona selecionando o mais barato

vértice adjacente enquanto olha para um único vértice. Você é encorajado a usar

heap binário para selecionar o vértice adjacente mais barato. Aqui a palavra

& # 8220mais barato & # 8221 significa aquele com o menor custo de borda. Escolha um ponto de partida

e continue adicionando vértices até que o heap esteja vazio. Você precisará inicializar

chaves de todos os vértices, exceto o ponto de partida para -INF, e atualizar a chave de um

determinado vértice quando é descoberto por seu vértice vizinho. Dê uma olhada em

https://en.wikipedia.org/wiki/Prim%27s_algorithm#Description para mais

exemplos e descrição do algoritmo.

Execute todos os algoritmos acima no contexto das seguintes questões em principal de

Graph.cpp e responda às seguintes perguntas. Você pode responder a essas perguntas em

forma de comentários no final do arquivo Graph.cpp.

1) Verifique a acessibilidade para os seguintes nós e deduza a natureza do conjunto de dados.

2) Para um gráfico com pesos de comprimento unitário, de quantos saltos Ali está

4) Quem tem menor valor de caminho em termos de índice de amizade?

5) Execute o MST no gráfico de peso unitário e gráfico ponderado. Poderia lá

existe mais de um MST para um dos gráficos? Que implicações você pode

tirar do resultado de ambas as execuções? Que benefício pode um site de mídia social

dos MSTs que você produziu? Você pode pensar em outro

aplicações do MST em termos de gráficos de conexão social?

Filas prioritárias na fila: https://www.geeksforgeeks.org/priority-queue-in-cppstl/

Você está convidado a usar a versão modelada do heap que você implementou no PA4 como um

substituição da fila prioritária e sua própria implementação / substituição do conjunto.


Contorno

Expansão e condutância do gráfico, gráficos expansores, desigualdade de Cheeger

Caminhadas aleatórias em gráficos, tempos de mistura, tempos de rebatidas, deslocamento e cobertura.

Árvores de abrangência aleatória e sua representação de rede elétrica

Árvores finas I, O (log (n) / loglog (n)) algoritmo de aproximação para TSP assimétrico

Esparsificação do gráfico I: amostragem independente, O (log (n)) esparsificadores para cortes e espectros

Polinômios de entrelaçamento I, distribuições estáveis ​​reais e suas propriedades

Árvores de abrangência aleatórias, novos algoritmos de aproximação para TSP

Polinômios de entrelaçamento II, problema de Kadison Singer

Esparsificação do gráfico II: duas vezes esparsificadores Ramanujan

Árvores finas II, representação espectral e lacuna de integralidade polylog (n) para ATSP

Probabilidade livre, convoluções finitas e gráficos Ramanujan


B8.5 Teoria dos gráficos - Material para o ano de 2020-2021

Os gráficos (redes abstratas) estão entre as estruturas matemáticas mais simples, mas ainda assim possuem uma teoria estrutural muito rica e bem desenvolvida. Uma vez que os gráficos surgem naturalmente em muitos contextos dentro e fora da matemática, a Teoria dos Grafos é uma área importante da matemática e também tem muitas aplicações em outros campos, como a ciência da computação.

O objetivo principal da unidade curricular é apresentar as ideias fundamentais da Teoria dos Grafos e algumas das técnicas básicas da combinatória.

O aluno terá desenvolvido uma compreensão básica das propriedades dos gráficos e uma apreciação dos métodos combinatórios usados ​​para analisar estruturas discretas.

Introdução: definições básicas e exemplos. Árvores e sua caracterização. Euler circunda caminhos e ciclos longos. Colorações de vértices: teorema de Brooks, polinômio cromático. Coloração das bordas: teorema de Vizing. Gráficos planos, incluindo fórmula de Euler, gráficos duais. Fluxo máximo - teorema do corte mínimo: aplicações incluindo o teorema de Menger e o teorema de Hall. Teorema de Tutte sobre as correspondências. Problemas extremos: teorema de Turan, problema de Zarankiewicz, teorema de Erd & # 337s-Stone.


5: Teoria dos grafos

Um gráfico acíclico (também conhecido como floresta) é um gráfico sem ciclos. Uma árvore é um grafo acíclico conectado. Assim, cada componente de uma floresta é uma árvore e qualquer árvore é uma floresta conectada.

Teorema O seguinte é equivalente em um gráfico G com n vértices.

  1. G é uma árvore.
  2. Existe um caminho único entre cada par de vértices em G.
  3. G está conectado e cada aresta em G é uma ponte.
  4. G está conectado e possui (n - 1) arestas.
  5. G é acíclico e possui (n - 1) arestas.
  6. G é acíclico e sempre que quaisquer dois vértices arbitrários não adjacentes em G são unidos por uma aresta, o grafo ampliado resultante G 'tem um ciclo único.
  7. G está conectado, e sempre que quaisquer dois vértices não adjacentes arbitrários em G são unidos por uma aresta, o gráfico ampliado resultante tem um ciclo único.

De um modo geral, os algoritmos associados às árvores podem ser divididos em três tipos.

  • Algoritmos para pesquisar e rotular uma determinada árvore.
  • Algoritmos para a construção de vários tipos de árvores.
  • Algoritmos para contar árvores de um tipo específico.

Árvore Uma árvore é um gráfico conectado que não contém ciclos.

Teorema Seja T um gráfico com n vértices. Então as afirmações seguintes são equivalentes.

  1. T está conectado e não contém ciclos.
  2. T está conectado e possui n-1 arestas.
  3. T tem n-1 arestas e não contém ciclos.
  4. T está conectado e cada aresta é abreviada.
  5. Quaisquer dois vértices de T são conectados por exatamente um caminho.
  6. T não contém ciclos, mas a adição de qualquer nova aresta cria exatamente um ciclo.

Seja G um grafo conectado. Uma árvore geradora em G é um subgrafo de G que inclui todos os vértices de G e também é uma árvore. As bordas das árvores são chamadas de galhos.

Por exemplo, considere o seguinte gráfico G

As três árvores abrangentes G são:

Podemos encontrar uma árvore geradora sistematicamente usando um dos dois métodos.

  • Método de corte
    • Comece escolhendo qualquer ciclo em G.
    • Remova uma das bordas do ciclo.
    • Repita este procedimento até que não haja mais nenhum ciclo.

    Por exemplo, dado o gráfico G

    1. Removemos a aresta ac que destrói o ciclo adca no gráfico acima e obtemos

    2. Removemos a aresta cb, que destrói o ciclo adcba no gráfico acima e obtemos

    3. Removemos a aresta ec, que destrói o ciclo decd no gráfico acima e, assim, obtemos a seguinte árvore geradora.

    • Método de construção
      • Selecione as arestas de G, uma de cada vez. de forma que nenhum ciclo seja criado.
      • Repita este procedimento até que todos os vértices sejam incluídos.

      Por exemplo, para o seguinte gráfico G

      2. Em seguida, escolha a aresta da seguinte maneira:

      3. Depois disso, escolha a aresta ec da seguinte forma:

      4. Finalmente, escolhemos a aresta cb e, assim, obtemos a seguinte árvore geradora.

      Teorema Um gráfico é conectado se e somente se tiver uma árvore estendida.

      Prova Seja G um grafo conectado. Exclua as arestas de G que não são pontes até obtermos um subgrafo conectado H em que cada aresta é uma ponte. Então H é uma árvore geradora. Por outro lado, se houver uma árvore geradora em G, há um caminho entre qualquer par de vértices em G, portanto, G está conectado.

      Centros e bicentros

      É conveniente começar a construir a árvore no meio de uma árvore e mover-se para fora. Essa foi a abordagem usada por Arthur Cayley ao contar o número de moléculas químicas, construindo-as passo a passo. Mas o que queremos dizer com o & quotmédio & quot de uma árvore?

      Existem duas maneiras diretas de centros de computação e bicentros.

      • Remova todos os vértices de grau1, junto com suas arestas incidentes.
      • Repita o processo até obter um único vértice (o centro) ou dois vértices unidos por uma aresta (o bicentro).

      Uma árvore com um centro é chamada de árvore central, e uma árvore com bicentro é chamada de árvore bicentral. Observe que toda árvore é central ou bicentral, mas não ambas.

      Por exemplo, dada a seguinte árvore.

      Remova todos os vértices de grau 1.

      Remova todos os vértices de grau 1.

      Portanto, uma árvore é central com centro e.

      Outro exemplo, dado a seguinte árvore.

      Remova todos os vértices de grau 1.

      Remova todos os vértices de grau 1.

      Portanto, uma dada árvore é bicentral com cd bicentro.

      Para cada vértice v do grau 2 ou mais, conte o número de vértices em cada uma das subárvores que emanam de v , e deixar n v ser o máximo desses números. Se a árvore tiver n vértices pode-se mostrar que existe apenas um vértice v para qual nv ≤ 1/2(n-1) (a árvore centróide ou centróide) ou há dois vértices adjacentes v e C para qual nv = nC = 1/2 n (a árvore bicentroid ou bicentroid). É fácil ver que toda árvore é centróide ou bicentroidal, mas não ambas.

      Observe que podemos pensar no centróide ou bicentroide como o 'centro de gravidade' da árvore.

      Por exemplo, dada a seguinte árvore

      Desde nc = 4, ne = 4, nf = 5 e ng = 6. Portanto, temos uma árvore bicentroidal com bicentroid ce.

      Outro exemplo, dado a seguinte árvore.

      Desde nb = 6, nc = 5, nd = 3 e nf = 5. Portanto, temos uma árvore centróide com centróide d.

      Existem dois métodos de pesquisa bem conhecidos. Eles são marrons como pesquisa em profundidade (DFS) e pesquisa em largura (BFS). Cada um desses métodos lista os vértices à medida que são encontrados e indica a direção em que cada aresta é percorrida primeiro. Os métodos diferem apenas na maneira como as listas de vértices são construídas.

      Pesquisa em profundidade (DFS)

      A ideia básica da pesquisa em profundidade é penetrar o mais profundamente possível em uma árvore antes de se espalhar para outros vértices. Essa ideia pode ser descrita da seguinte forma:

      Outro exemplo, a expressão a + <(b-c) d> pode ser representada pela seguinte árvore:

      Exemplo: considere o gráfico

      Observe que marcamos as arestas que usamos ao ir para o novo vértice. Essas arestas formam uma árvore estendida, chamada de árvore estendida DFS.

      Pesquisa ampla (BFS)

      A ideia básica da pesquisa em largura é espalhar o máximo possível de vértices antes de penetrar profundamente em uma árvore. Essa ideia pode ser descrita da seguinte forma:

      O exemplo acima mostra claramente que a pesquisa em amplitude deve completar cada nível antes de prosseguir para o próximo.

      Exemplo: considere o gráfico

      Observe que marcamos as arestas que usamos ao ir para o novo vértice. Essas arestas formam uma árvore estendida, chamada de árvore estendida BFS.


      Assista o vídeo: Aula 5 Exercícios e Introdução à Teoria Dos Grafos (Outubro 2021).