COLORAÇÃO E PLANARIDADE EM GRAFOS

REGISTRO DOI: 10.70773/revistatopicos/778816145

RESUMO
Este trabalho tem como objetivo explorar avanços na teoria dos Grafos e conexões com os grupos, além de estudar características como a dimensão métrica, para descobrir mais relações entre planaridade e coloração de Grafos. Também será abordado como Planaridade e Coloração estão presentes na teoria de Grafos Associados a Grupos cíclicos e o que esses conceitos podem revelar sobre a estrutura desses objetos. Além disso, serão apresentados alguns resultados obtidos ao longo do projeto.
Palavras-chave: Grafos; Planaridade; Coloração; Dimensão métrica; Grupos.

ABSTRACT
This work aims to explore advances in graph theory and connections with groups, as well as to study characteristics such as metric dimension, to discover more relationships between planarity and coloring of graphs. It will also address how planarity and coloring are present in the theory of graphs associated with cyclic groups and what these concepts can reveal about the structure of these objects. In addition, some results obtained throughout the project will be presented.
Keywords: Graphs; Planarity; Coloring; Metric dimension; Groups.

1. INTRODUÇÃO

Grafos são objetos matemáticos que foram desenvolvidos primeiramente por Euler para resolver o problema das 7 pontes de Konigsberg. Eles se tornaram peças importantes tanto no estudo de grupos quanto em áreas da informática, como análise de redes e conexões. Neste estudo, iremos nos limitar a estudar a planaridade e a coloração desses objetos, temas que geram debate há algum tempo. Embora já exista algoritimos para descobrir a estas características, tentamos obter novas tecnícas para inferir estas propriedades para certos tipos de Grafos, além de estabelecer principalmente o número cromático de Grafos associados a Grupos cíclicos e compreender o que o número cromático revela sobre a estrutura desses grafos.

2. O que é um Grafo? E suas propriedades

Um grafo G = G(V,E) é um par, onde V é um conjunto não vazio que representa os vértices e E é um conjunto de subconjuntos de 2 elementos de V.

Este é um exemplo clássico de um grafo, conhecido como grafo completo de 4 vértices. Um grafo completo é um grafo no qual todos os vértices estão conectados entre si, sendo denotado por K_n, em que o ’K’ indica que o grafo pertence à família de grafos completos e ’n’ representa o número de vértices.

Como se pode observar, esse é um conceito simples e intuitivo. Na teoria dos Grafos, chamamos os pontos de vértices e as ligações de arestas. Neste estudo, iremos nos limitar, inicialmente, a grafos simples, não orientados, conexos e finitos. Um grafo simples é aquele em que entre dois vértices só existe uma aresta, e nenhum vértice possui uma aresta consigo mesmo, o que é chamado de laço. Um grafo não orientado é aquele em que não é definida uma direção na aresta, ou seja, não há problema em percorrer a aresta de um vértice para outro. Um grafo conexo é aquele em que é possível, através de um caminho finito, chegar de um vértice a qualquer outro vértice do conjunto. Por fim, um grafo finito é aquele em que o número ’n’ de vértices é finito.

2.1. Grau

Definido o que é um grafo, apresentaremos importantes propriedades para o entendimento do artigo.

O grau de um vértice é o número de arestas incidentes a ele. No grafo complexo mostrado acima, o grau do vértice A é 3 e o do vértice B é 2. A priori, o grau varia de vértice para vértice. No entanto, existem grafos em que essa propriedade é uma constante, independente do vértice analisado, como o K₃ e o K₄, que foram apresentados anteriormente. Esses grafos possuem todos os vértices com o mesmo número de arestas incidentes, e são chamados de r-regulares. Por exemplo, o K₃ é 2-regular, enquanto o K₄ é 3-regular. É possível mostrar que todo grafo K_n é (n-1)-regular.

2.2. Passeio, Caminho, Distância, Diâmetro e Ciclo

Temos também as definições de passeio e caminho. Um passeio é uma lista de vértices em que cada vértice possui uma aresta que o conecta ao próximo. Um caminho é um passeio em que nenhum vértice se repete. O comprimento de cada uma dessas listas é o número de arestas percorridas durante um passeio no grafo.

Considere o grafo abaixo e o seguinte passeio: 5-1-2-3-6-2-3. No entanto, se quisermos encontrar o caminho entre, por exemplo, 1 e 3, devemos selecionar um passeio em que nenhum vértice se repita. No exemplo acima, o caminho entre 1 e 3 seria 1-2-3, um caminho de tamanho 3.

Dentro da definição de caminho, temos as definições de distância e diâmetro de um grafo. A distância d(v1, v2), onde v1 e v2 são dois vértices arbitrários, é o menor caminho entre esses dois vértices. O diâmetro é a maior distância entre todos os pares de vértices em um grafo e é representado por ∆(G_n).

Um ciclo dentro de um grafo é um passeio de tamanho mínimo 3, em que nenhum vértice, exceto o primeiro e o último, se repete.

2.3. Coloração

Agora serão definidas as principais características que serão abordadas neste artigo: coloração e planaridade. A coloração de um grafo consiste em atribuir uma cor a cada vértice, com a restrição de que vértices adjacentes recebam cores diferentes.

Por exemplo, na Figura 1 é apresentada a coloração de um grafo, em que cada vértice é representado por um círculo e as cores são indicadas por diferentes tonalidades. Observa-se que vértices adjacentes possuem cores distintas.

É importante destacar que se escolhermos o número de cores igual ao número de vértices, a tarefa de colorir o grafo se torna trivial. No entanto, o objetivo principal é encontrar o menor número de cores necessárias para realizar a coloração. Esse número é chamado de número cromático, denotado por χ(G). Nos exemplos acima, χ(G) é igual a 3 e 4, respectivamente (Figura 1 e Figura 2).

Assim, o foco principal é encontrar o menor número de cores necessário para realizar a coloração de um grafo, buscando soluções eficientes e otimizadas.

2.4. Planaridade

O problema de planaridade está relacionado à capacidade de desenhar um grafo em um plano, de forma que as arestas não se cruzem. Um grafo que pode ser desenhado dessa maneira é chamado de grafo planar, enquanto um grafo que não pode ser desenhado sem cruzamento de arestas é chamado de grafo não planar. Embora possa parecer um problema simples, determinar a não planaridade de um grafo é uma tarefa complexa devido ao grande número de desenhos diferentes que podem representar o mesmo grafo. O leitor pode encontrar mais informações no capítulo 53 da referência [6]] e no capítulo 3 do [7]].

Na Figura 1, 2, 3 e 7 são apresentados exemplos de grafos planares, nos quais as arestas são desenhadas sem se cruzar. Por outro lado, nas Figuras 4 e 6 são mostrados exemplos de grafos não planares, nos quais não é possível desenhar as arestas sem que elas se cruzem. Existem infinitos grafos em ambas as categorias, mas dois grafos são especialmente importantes no estudo da planaridade: o K₅ e o grafo utilitário K_3,3.

O grafo K₅, ilustrado na Figura 8, é o menor grafo completo não planar. O grafo utilitário K_3,3, mostrado na Figura 9, é outro exemplo de grafo não planar importante. Todo grafo não planar pode ser expandido ou possui esses grafos como subgrafos. Esses dois grafos desempenham um papel fundamental no estudo da planaridade e fornecem uma base para entender a estrutura dos grafos não planares.

Um dos teoremas mais importantes no estudo da planaridade e coloração é o Teorema de Kuratowski, que afirma que todo grafo que possui um subgrafo que é uma subdivisão de K₅ ou K_3,3 é não planar. Em outras palavras, se um grafo contém um subgrafo que pode ser obtido adicionando um vértice entre uma aresta qualquer e gerando K₅ ou K_3,3, então ele é não planar. Esses teoremas serão de suma importância nas seções futuras e podem ser facilmente verificados nas referências do trabalho [6]] e [7]].

3. Notações e Teoremas

Definimos um grafo G com número de vértices |V| e conjunto de arestas |E|, denotado por G = (V,E), onde V é um conjunto finito de vértices e E é um conjunto de subconjuntos de 2 elementos de V. É comum escrever G_n quando queremos destacar o número de vértices. Exemplo: G₃ = ([1,2,3];[1,3],[2,3])

Grafos importantes:

• P_n = Grafo de caminho com n vértices.

• K_s,t = Grafo onde se possa dividir os vértices em 2 subconjuntos, onde nenhum par de vértices do mesmo subconjunto possua aresta entre si.

• T_n = Arvoré de n vértices, não possui nenhum ciclo dentro de si.

• C_n = Ciclo de n vértices.

• K = Grafo que não possui vértices.

• V_n = Grafo que não possui arestas.

• H_n ⊆ G_n = Subgrafo H de G, tal que V_H ⊆ V_G e E_H ⊆ E_G

• M_n = Grafo planar maximal, ou seja, um grafo planar para o qual a adição de qualquer aresta ao subconjunto de arestas torna-o não planar.

Lemas importantes:

A soma dos graus dos vértices de um grafo é igual a duas vezes o número de arestas:

(1)

A fórmula de Euler para grafos planares: V + F - E = 2, onde F é o número de regiões delimitadas pelo grafo.

(2)

Seja H_n ⊆ G_n. Então:

(3)

Grafos Planares:

(4)

(5)

4. Dimensão Métrica

A Dimensão Métrica é a mínima cardinalidade de um conjunto de vértices W tal que todos os vértices podem ser diferentemente representados por suas distâncias em relação aos vértices de. Para se encontrar a dimensão métrica de um dado Grafo, basta encontrar tal conjunto W de forma que não exista nenhum outro conjunto de cardinalidade menor.

O conjunto Resolvedor do K₅ (Figura: 8) sendo W = { 1, 2, 3 ,4 } e o do K_3,3 (Figura:9) = {1,3,4,6}

Após a determinação do conjunto resolvedor em questão, podemos definir o Grafo a partir das distâncias relativas encontradas.

Tabela 1: Resolução do K5

COLORAÇÃO E PLANARIDADE EM GRAFOS

Como pode ser observado, o conjunto mencionado de fato resolve o Grafo, associando a cada vértice um vetor diferente. Agora podemos definir a dimensão métrica de um Grafo G_n como o valor mínimo da cardinalidade de um conjunto resolvedor para G_n. A representação mostrada acima na tabela pode ser denotada como uma sequência r(v|W) = (d(v,w₁),d(v,w₂),...,d(v,w_k)), onde cada linha da tabela corresponde a um r(v_n|W).

Antes de abordar o que foi produzido, irei começar enunciando alguns lemas de importância na área.

(6)

(7) 

(8) 

Teoremas:

Caso dim(G_n) = 2:

Então G_n não possui K₅,K5 − e e K_3,3 como subgrafos. (T.1) [1]]

Não existe nenhum subgrafo tal que ∆ ≤ ^p|V | − 1 (T.2) [1]] |V (G)| < D − 1 + 8 (T.3) [10]] seja {V_n,V_l} uma base do conjunto resolvedor, o grau de V_n ou V_l é no maximo 3 e o grau de qualquer outro vértice é no máximo 5. (T.4) [1]] Existem Grafos não planares com dim(G_n) = 2. (T.4) [1]]

Resultados:

Através da observação da relação entre as possíveis distâncias entre um par arbitrário de vértices, temos que qualquer vértice, quando representado de acordo com o conjunto resolvedor, terá no máximo ∆ + 1 possibilidades de representação. Pelo Princípio das casas dos Pombos, que nos diz que se existem n+1 pombos para n casas, pelo menos uma casa terá dois pombos. Portanto, pelo principio das casas dos pombos temos que:

(11)

Colocando a restrição de que o grafo é planar e utilizando as relações da seção 3, podemos inferir limites e relações mais precisas entre o número de vértices, arestas e diâmetros de G_n e sua dimensão métrica. Usando as relação: (2),(4),(5) e (10), temos:

(12) 

(13) 

Para Grafos planares com dim(G_n) = 2, podemos estabelecer relações entre o número de arestas, vértices e grau do Grafo para obter limites superiores para o diâmetro, utilizando as relações (1) e (T.4).

(14)

(15)

(16)

5. GRUPOS E GRAFOS ASSOCIADOS

Chamamos de grupo um conjunto de elementos associados a uma operação que combina dois elementos quaisquer para formar um terceiro, sujeito às seguintes condições:

1. Fecho: Para qualquer operação entre a e b pertencentes a um grupo H, temos que c = a ∗ b também pertence ao grupo H.

2. Associatividade: Para a, b e c pertencentes a G, temos que a∗(b∗c) = (a ∗ b) ∗ c.

3. Elemento neutro: Existe um elemento e em H tal que e∗a = a∗e = a para qualquer a em H.

4. Elemento simétrico: Para qualquer a em H, existe um elemento a^′ tal que a^′ ∗ a = a ∗ a^′ = e.

Sabendo o que é um grupo, existe um teorema que relaciona grupos e grupos simétricos, que afirma que todo grupo é isomorfo a um subgrupo do grupo simétrico de G, denotado por Sim(G). Nesse grupo, os elementos são permutações de um subconjunto de G.

Embora não seja nosso objetivo explorar a teoria dos grupos em detalhes, ou discutir o teorema em questão, é importante destacar que, a partir do fato de todo grupo ser isomorfo a um grupo de permutações, podemos representar a teoria dos grupos utilizando a teoria dos grafos e estudar a estrutura dos grupos dessa maneira.

Se G = ⟨S⟩, podemos considerar o seguinte grafo associado: G(V,E), onde os vértices são denotados por V (v|v ∈ G) e as arestas por E(G) = {(v,u)|gv = u para algum g ∈ S}. Esse grafo associado é chamado de grafo de Cayley de G e é denotado por Cay(S : G).

Exemplos:

D₄ =< a,b|a⁴ = e = b²,bab = a³ >

Pode-se observar pelo exemplo que cada aresta é colorida com uma cor associada a cada elemento do conjunto gerador S que gera G. No exemplo acima, o elemento b recebe a cor azul e o elemento a recebe a cor vermelha. Os grafos de Cayley são, por padrão, orientados e são conhecidos como dígrafos. No entanto, quando a operação é auto-inversível, ou seja, existe um elemento s ∈ S tal que s = s⁻¹, o grafo de Cayley correspondente não tem orientação privilegiada. Podemos observar que b é auto-inversível, o que significa que as operações envolvendo b não possuem uma direção específica.

Ao estudar os grafos de Cayley associados ao conjunto de grupos D_n, constatou-se que a estrutura desses grafos é regular, o que nos permite inferir que:

Cay({a,b} : D_n), onde D_n =< a,b|aⁿ = e = b²,bab = a⁻1 > são:

• 3-regulares

• ∆(Cay({a,b} : D_n)) = n − 1

• χ(Cay({a,b} : D_n)) = 3 se n for impar e χ(Cay({a,b} : D_n)) = 2 se n for par

• as direções das operações são invertidas quando se passa de aⁿ para baⁿ

• São planares.

• Dim(Cay({a,b} : D_n)) não obedecem aos lemas colocados na seção passada, alias, a dimensão métrica de um Grafo de Cayley de D_n é n. [3]]

Através do número cromático, podemos determinar quantas subdivisões existem em um determinado grafo. Por exemplo, um grafo com χ = 2 é um grafo que pode ser subdividido em 2 partes, de forma que nenhum par de vértices da mesma parte tenha uma aresta entre si. Isso é conhecido como um grafo bipartido. Com base nos resultados mencionados anteriormente para os grupos diédricos D_n, podemos afirmar que todos os grupos diedrais de ordem n par são bipartidos, enquanto os de ordem n ímpar são tripartidos. Podemos dividir os elementos em subconjuntos de forma que nenhum elemento do mesmo subconjunto seja gerado por um elemento de S. Vale ressaltar que todos os grupos desse conjunto mantêm a propriedade de serem planares.

Definir qual a dimensão métrica de um Grafo Cayley, ainda é um problema em aberto que requer uma abordagem diferente da convencional devido à estrutura orientada dos grafos associados. No entanto, existe um teorema que permite determinar quais grafos de Cayley possuem dim(Cay(S : G)) = 2. Esse teorema é o seguinte:

Seja G um grupo abeliano de ordem n > 4 e S um subconjunto de G, onde e não está em S e S é igual ao seu inverso.

Então, temos que dim(Cay(S : G)) = 2 se e somente se G é gerado por um único elemento, ou seja, G é cíclico, e S é dado por:

onde mdc(i, n/2) = 1 e n é congruente a 2 mod(4).[3]]

Esse teorema ilustra a dificuldade em falar sobre a dimensão métrica em objetos como os grafos de Cayley. No entanto, ainda conseguimos definir essa propriedade e obter resultados a partir dela.

6. GRAFOS NÃO COMUTANTES

Um Grafo não comutante é uma representação de um Grupo na qual os vértices são elementos não centrais do grupo e o conjunto de arestas é dado por: dois elementos estão ligados se, e somente se, eles comutam.

O Grupo Diedral que é o Grupo de simetria de um poligono regular de n lados é definido como D_n =< a,b|aⁿ = 1 = b²,bab = aⁿ⁻¹ >, n ≤ 3. Caso n seja par, o centro o conjunto dos elementos {a2 ,1} e se for ímpar o centro é trivial sendo composto somente do elemento neutro 1.

Nos exemplos ... evidenciamos que os grafos associados são bem comportados. Temos o seguinte resultado:

Proposição 6.1. Seja n ≥ 3. Seja D_n o grafo não comutante associado ao grupo diedral D_n.

• Se n é ímpar, então não existem arestas entre as involuções. Ou seja, os elementos da forma ba^k são isolados, k ∈ {0,1,...,n − 1}.

  

• Se n é par, então cada involução (não central) tem grau 1. Mais precisamente, ba^k e ba^k+n/2 formam um clique.

Teorema 6.1. Seja n ≥ 3. Seja D_n o grafo não comutante associado ao grupo diedral D_n.

• χ(D_n) = n − 2, se n é par; n − 1 se n é ímpar.

• D_n tem componentes, se n é par; n+1, se n é ímpar.

• D_n é planar se, esomente se n ≤ 5.

7. CONSIDERAÇÕES FINAIS

Este trabalho estuda os diferentes tipos de Grafos formados por diferentes relações e busca através de caractéristicas gerais de um Grafo tentar encontrar uma relação entre estas e planaridade e coloração. Conseguimos através da suposição de planaridade achar limites superiores para a dimensão métrica, além de conseguir relacionar o diametro de um Grafo com seu número de arestas. Conseguimos também encontrar diversas relações para Grafos de Cayley relacionado ao D_n, além de conseguir mostrar como se constroí um Grafo associado não comutativo para o D_n qualquer que seja o n.

REFERÊNCIAS BIBLIOGRÁFICAS

1. A. Behtoei, A. Davoodi, M. Jannesari, and B. Omoomi, "A characterization of some graphs with metric dimension two,"arXiv:1509.02129 [math.CO], 2015.

2. G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, "Resolvability in graphs and the metric dimension of a graph,"Discrete Applied Mathematics, vol. 105, no. 1, pp. 99-113, 2000.

3. M. Fehr, S. Gosselin, and O. R. Oellermann, "The metric dimension of Cayley digraphs,"Discrete Mathematics, vol. 306, no. 1, pp. 31-41, 2006.

4. F. Harary, R. A. Melter, "On the metric dimension of a graph,"Ars Combinatoria, vol. 2, no. 191-195, pp. 1, 1976.

5. S. Khuller, B. Raghavachari, and A. Rosenfeld, "Landmarks in graphs,"Discrete Applied Mathematics, vol. 70, no. 3, pp. 217-229, 1996.

6. E. R. Scheinerman, Matemática Discreta: Uma introdução - Tradução da 3ª ed. norte-americana, Cengage Learning Brasil, 2016.

7. R. J. Trudeau, Introduction to Graph Theory, Dover Publications, 2013.

8. E. Vatandoost, A. Behtoei, and Y. G. Pour, "Cayley graphs with metric dimension two - A characterization,"arXiv:1609.06565 [math.CO], 2016.

9. L. Eroh, C. Kang, and E. Yi, "The connected metric dimension at a vertex of a graph,"Theoretical Computer Science, vol. 806, Apr. 2018.

10. G. Sudhakara and H. Kumar, "Graphs with Metric Dimension Two: A Characterization,"Advances and Applications in Discrete Mathematics, vol. 4, Dec. 2009.