Analisando Gráficos Sem Link em Superfícies de Donut

Gráficos são tipo pontos conectados por linhas. Você pode imaginar eles como desenhos feitos de pontos e caminhos. Alguns desses desenhos podem se torcer e virar sem emaranhar e são chamados de sem ligação. Agora, imagine que você quer desenhar esses gráficos em uma superfície em forma de donut. Parece simples, mas tem uma pegadinha (trocadilho intencional). Se o gráfico se emaranhar enquanto você desenha no donut, ele se torna um gráfico ligado. Este estudo é sobre descobrir quais gráficos podem ser desenhados em um donut sem emaranhar, especialmente quando os gráficos não estão ligados entre si.

#Fundo: Gráficos e seus Tipos

Para entender o que tá rolando, precisamos falar sobre alguns termos básicos.

• Gráficos Planares: Esses são gráficos que podem ser desenhados em uma superfície plana sem linhas se cruzando. Pense em desenhar com giz de cera no papel.

• Gráficos Toroidais: Esses são gráficos que podem ser desenhados em uma superfície em forma de donut sem cruzar linhas. É como tentar fazer sua arte de giz em um brinquedo inflável de piscina.

• Gráficos Sem Ligação: Imagine duas linhas que podem se torcer uma em volta da outra sem fazer um nó. Isso é o que queremos dizer com sem ligação. É importante porque queremos que nossos desenhos de gráficos evitem ficar emaranhados.

No mundo dos gráficos, alguns são naturalmente mais complexos, enquanto outros são simples. Se um gráfico pode ser desenhado em um donut sem que as linhas se cruzem, ele é chamado de toroidal. Se ele pode ser desenhado naquele donut sem que as linhas fiquem amarradas umas nas outras, ele é sem ligação ou não intrinsecamente ligado (nIL para abreviar).

#A Grande Pergunta

A pergunta que queremos responder é: se temos um gráfico que pode ser desenhado em um donut e também é sem ligação, podemos garantir que conseguimos desenhá-lo sem emaranhados em uma forma padrão de donut?

Até agora, sabemos que para gráficos menores (com até 9 pontos), se eles podem ser desenhados no donut e evitam emaranhados, podemos dizer com confiança que eles também podem ser desenhados em uma forma padrão de donut. Mas e os gráficos maiores?

#Ligações no Donut

Vamos falar sobre ligações. Ligações são como aqueles momentos chatos quando duas pessoas tentam passar uma pela outra em um corredor e acabam se emaranhando.

• Número de Ligação: Existe uma maneira de medir o quão emaranhados dois caminhos estão. Podemos contar como esses caminhos se cruzam. Se eles se cruzam e torcem de uma certa maneira, atribuimos valores a eles. No final do dia, se o valor total não for zero, eles estão emaranhados.

#Explorando Famílias de Gráficos

Podemos agrupar gráficos com base em características comuns, meio que como um clube de amigos com hobbies similares.

• Famílias Fechadas por Menor: Esses são grupos de gráficos que não mudam sua natureza quando você remove ou diminui algumas de suas partes. Se você faz parte desse clube, não pode fazer parte de outro clube que não permita certos membros.

Temos dois clubes principais no nosso estudo: o clube dos gráficos toroides e o clube dos gráficos sem ligação. Todos os gráficos sem ligação também são gráficos toroides, mas nem todos os gráficos toroides são sem ligação. Pense nisso como ser uma pessoa que ama gatos; todas as pessoas que amam gatos gostam de pets, mas nem todos os amantes de pets preferem gatos.

#Gráficos MaxnIL e Sua Importância

Às vezes, encontramos gráficos especiais que estão no topo da cadeia. Esses são chamados de gráficos maxnIL. Eles são sem ligação e não podem ter arestas extras adicionadas sem se tornarem ligados. Eles são como os grandes chefões na comunidade de gráficos sem ligação.

A maior parte do nosso estudo foca nesses gráficos maxnIL porque se conseguirmos descobrir como desenhá-los de forma sem ligação em um donut, podemos também trabalhar para trás e ver se isso se aplica a todos os outros gráficos.

#Obstruções Toroidais

Enquanto exploramos o mundo dos gráficos toroides, encontramos alguns que não se encaixam na descrição de sem ligação. Esses são chamados de obstruções toroides, e são como os convidados indesejados que estragam a festa.

Até agora, descobrimos algumas obstruções toroides que não podem ser desenhadas sem ligação sem torcer. A menor delas tem 8 pontos e é a primeira que precisamos expulsar do clube sem ligação.

#Encontrando Gráficos MTN

Para responder à grande pergunta, precisamos descobrir quais gráficos podem ser desenhados sem ligação em um donut sem emaranhar. Começamos com gráficos menores e vamos subindo.

Para os gráficos menores (como os com 6 ou 7 pontos), podemos afirmar com confiança que são sem ligação. À medida que subimos, o desafio se torna mais complexo, especialmente quando encontramos gráficos de ordem 9.

#A Busca pela Sem Ligação

Quando investigamos gráficos de ordem 9, usamos uma variedade de técnicas e observações. Temos uma compreensão prévia de que certos gráficos não podem ser ligados.

Através de uma série de deduções inteligentes, podemos determinar que dos vinte gráficos maxnIL de ordem 9, apenas quatro não podem ser desenhados no donut sem emaranhar. Esses quatro encrenqueiros tornam nossas vidas mais interessantes, mas também complicam nossa pesquisa.

#Ferramentas do Comércio

Ao longo dessa jornada, usamos vários algoritmos para nos ajudar a acompanhar quais gráficos estamos lidando. Aplicando esses algoritmos, podemos delinear condições que determinam se um gráfico pode ser desenhado sem ligação ou não.

Um algoritmo útil nos ajuda a identificar gráficos sem ligação com base nos cruzamentos de caminho. Isso é crucial porque nos economiza de desenhar cada gráfico à mão. Afinal, quem tem tempo pra isso?

#Provando a Sem Ligação

Agora que temos uma compreensão sólida dos gráficos com os quais estamos trabalhando, é hora de provar que um gráfico é sem ligação. Usamos nossa definição anterior de inclinações e cruzamentos e podemos fazer um pequeno teste. Se a lista retornada pelo nosso algoritmo não mostrar conflitos ou emaranhados, podemos dizer com confiança que o gráfico é sem ligação.

#Os Resultados

Depois de horas e horas desenhando, examinando e testando, coletamos uma coleção completa de gráficos MTN para ordens que variam de 6 a 9. As descobertas indicam que todos esses gráficos podem ser desenhados em um donut sem emaranhar, então festa!

#Direções Futuras

Depois de lidar com os gráficos menores, agora queremos ver se conseguimos estender esse trabalho para gráficos maiores. Acreditamos que há uma boa chance de que todos os gráficos toroidais, nIL possam ser desenhados sem ligação em um donut.

Fizemos progressos significativos, mas o futuro vai exigir muito trabalho. Entender os menores proibidos para esses tipos de gráficos pode eventualmente nos levar a conclusões mais fortes sobre seu comportamento sem ligação.

#Conclusão

Em resumo, fizemos uma divertida imersão no mundo dos gráficos em donuts, descobrindo como essas formas matemáticas podem existir sem se emaranhar. Com nossas descobertas, agora temos uma noção melhor de como esses gráficos funcionam em uma superfície toroidal, e embora ainda haja mais a explorar, estamos felizes por termos provado uma coisa: nem todos os gráficos gostam de se emaranhar, e isso é um alívio.