grafos:colarestas

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:colarestas [2023/06/12 14:43] – pivagrafos:colarestas [2023/06/21 20:59] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
-===== Colorações de arestas =====+==== Colorações de arestas ====
  
 De maneira similiar a uma [[.numerdecores | coloração de vértices]], entederemos por [[.defcolarestas | coloração de arestas]] de um grafo $G = (V,E)$ uma função $c: E \to \{1,2,\dots,n\}$ tal que $c(e) \neq c(f)$ se $e$ e $f$ forem arestas adjacentes, isto é, possuírem uma extremidade em comum. Em particular, essa é uma coloração dos vértices do [[.linegraph | grafo das arestas]] de $G$. Nesse sentido, o menor número $n$ para o qual existe uma coloração de arestas $c: E \to  \{1,2,\dots,n\}$ para $G$ é dito ser o [[.defcolarestas | número cromático de arestas]] desse grafo, denotado por [[.defcolarestas | $\chi'(G)$]]. Como antes $\{1,2,\dots,n\}$ é designado como o conjunto de cores da coloração. De maneira similiar a uma [[.numerdecores | coloração de vértices]], entederemos por [[.defcolarestas | coloração de arestas]] de um grafo $G = (V,E)$ uma função $c: E \to \{1,2,\dots,n\}$ tal que $c(e) \neq c(f)$ se $e$ e $f$ forem arestas adjacentes, isto é, possuírem uma extremidade em comum. Em particular, essa é uma coloração dos vértices do [[.linegraph | grafo das arestas]] de $G$. Nesse sentido, o menor número $n$ para o qual existe uma coloração de arestas $c: E \to  \{1,2,\dots,n\}$ para $G$ é dito ser o [[.defcolarestas | número cromático de arestas]] desse grafo, denotado por [[.defcolarestas | $\chi'(G)$]]. Como antes $\{1,2,\dots,n\}$ é designado como o conjunto de cores da coloração.
Linha 17: Linha 17:
 Suponha então que $i \neq j$ e, além disso, que existem uma aresta $e$ de cor $j$ com ponta em $x$ e uma aresta $f$ de cor $i$ incidente em $y$. Nesse caso, considere um [[.walk | passeio]] $W$ maximal em $H$ contendo $e$ e cujas demais arestas têm cores $i$ ou $j$. Em particular, como arestas adjacentes estão coloridas com cores distintas, nesse passeio não deve haver um vértice de grau maior ou igual a $3$. Logo, como nenhuma aresta de cor $i$ incide em $x$, [[.auxiliarbrooks | o passeio $H$ é na verdade um caminho]]. Uma de suas extremidades trivialmente é o vértice $x$. A outra, contudo, não pode ser $y$: se fosse, a aresta de $W$ que incide em $y$ deve ser a $f$, pois nenhuma aresta de cor $j$ incide nesse vértice. Portanto, como $W$ é um caminho formado por arestas de cores $i$ e $j$ alternadamente, obtemos que $E(W)\cup \{xy\} $ é um conjunto de arestas que define um ciclo ímpar, [[.defbipartite | contradizendo]] o fato de $G$ ser um grafo bipartido. Destacamos também que $y$ não pode ser um vértice de grau $2$ em $W$, pois, nesse caso, alguma aresta de cor $j$ (do próprio caminho $W$) teria ponta em $y$. Suponha então que $i \neq j$ e, além disso, que existem uma aresta $e$ de cor $j$ com ponta em $x$ e uma aresta $f$ de cor $i$ incidente em $y$. Nesse caso, considere um [[.walk | passeio]] $W$ maximal em $H$ contendo $e$ e cujas demais arestas têm cores $i$ ou $j$. Em particular, como arestas adjacentes estão coloridas com cores distintas, nesse passeio não deve haver um vértice de grau maior ou igual a $3$. Logo, como nenhuma aresta de cor $i$ incide em $x$, [[.auxiliarbrooks | o passeio $H$ é na verdade um caminho]]. Uma de suas extremidades trivialmente é o vértice $x$. A outra, contudo, não pode ser $y$: se fosse, a aresta de $W$ que incide em $y$ deve ser a $f$, pois nenhuma aresta de cor $j$ incide nesse vértice. Portanto, como $W$ é um caminho formado por arestas de cores $i$ e $j$ alternadamente, obtemos que $E(W)\cup \{xy\} $ é um conjunto de arestas que define um ciclo ímpar, [[.defbipartite | contradizendo]] o fato de $G$ ser um grafo bipartido. Destacamos também que $y$ não pode ser um vértice de grau $2$ em $W$, pois, nesse caso, alguma aresta de cor $j$ (do próprio caminho $W$) teria ponta em $y$.
  
-Então, observamos que é possível trocar em $W$ as cores $i$ e $j$ sem que arestas adjacentes recebam cores iguais, por conta da maximalidade de $W$ como passeio com arestas de cores $i$ ou $j$. Isso descreve uma coloração de arestas em que nenhuma aresta de cor $j$ incide em $x$. Afinal, a aresta $e$, a única que possuía essa cor e tinha esse vértice como extremidade, tem agora cor $i$. Da mesma forma, nenhuma aresta de cor $j$ incide em $y$, pois trocamos apenas cores de arestas do caminho $W$. Essa nova coloração, portanto, pode ser estendida para todo o grafo $G$ ao colorirmos a aresta $xy$ com a cor $j$.  <wrap right>$\square$</wrap>   +Então, observamos que é possível trocar em $W$ as cores $i$ e $j$ sem que arestas adjacentes recebam cores iguais, por conta da maximalidade de $W$ como passeio com arestas de cores $i$ ou $j$. Isso descreve uma coloração de arestas em que nenhuma aresta de cor $j$ incide em $x$. Afinal, a aresta $e$, a única que possuía essa cor e tinha esse vértice como extremidade, tem agora cor $i$. Da mesma forma, nenhuma aresta de cor $j$ incide em $y$, pois trocamos apenas cores de arestas do caminho $W$. Essa nova coloração, portanto, pode ser estendida para todo o grafo $G$ ao colorirmos a aresta $xy$ com a cor $j$.   
 + 
 +<wrap right>$\square$</wrap>    
 +</WRAP> 
 + 
 +----
  
 Diferentemente da teoria de colorações de vértices, a teoria de coloração de arestas é capaz de determinar um excelente limitante superior para o número mínimo de cores a serem utilizadas. Com o resultado a seguir, tem-se que, para todo grafo $G$, a grandeza $\chi'(G)$ assume no máximo dois valores: $\Delta(G)$ ou $\Delta(G)+1$. Apesar disso, não existem caracterizações ou indícios claros de quando cada um desses valores é assumido. Diferentemente da teoria de colorações de vértices, a teoria de coloração de arestas é capaz de determinar um excelente limitante superior para o número mínimo de cores a serem utilizadas. Com o resultado a seguir, tem-se que, para todo grafo $G$, a grandeza $\chi'(G)$ assume no máximo dois valores: $\Delta(G)$ ou $\Delta(G)+1$. Apesar disso, não existem caracterizações ou indícios claros de quando cada um desses valores é assumido.
  
 <WRAP round box 100%> <WRAP round box 100%>
-**Teorema (** Vizing **):** //Para qualquer grafo $G = (V,E)$, tem-se $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$.//+=== Teorema (Vizing) ===  
 +//Para qualquer grafo $G = (V,E)$, tem-se// 
 + 
 +$$\Delta(G) \leq \chi'(G) \leq \Delta(G)+1.$$
 </WRAP> </WRAP>
  
-__//Demonstração://__ A desigualdade $\Delta(G) \leq \chi'(G)$ foi estabelecida anteriormente. Por indução sobre a quantidade de arestas de $G$, então, mostraremos que $\chi'(G) \leq \Delta(G)+1$. O caso base desse processo indutivo, em que $|E| = 0$, é trivialmente verificado. Caso $G$ tenha uma aresta $xy \in E$, utilize a hipótese indutiva para fixar uma coloração das arestas de $G\setminus xy$ com cores em $\{1,2,\dots, \Delta(G)+1\}$. Observamos que isso é possível pois $\Delta(G\setminus xy) \leq \Delta(G)$.+<WRAP round box 100%> 
 +**//Demonstração://**  
 + 
 +A desigualdade $\Delta(G) \leq \chi'(G)$ foi estabelecida anteriormente. Por indução sobre a quantidade de arestas de $G$, então, mostraremos que $\chi'(G) \leq \Delta(G)+1$. O caso base desse processo indutivo, em que $|E| = 0$, é trivialmente verificado. Caso $G$ tenha uma aresta $xy \in E$, utilize a hipótese indutiva para fixar uma coloração das arestas de $G\setminus xy$ com cores em $\{1,2,\dots, \Delta(G)+1\}$. Observamos que isso é possível pois $\Delta(G\setminus xy) \leq \Delta(G)$.
  
 Para descrevermos uma coloração para o grafo $G$, faremos uso de certas notações auxiliares. Primeiro, diremos que uma cor $1 \leq i\leq \Delta(G)+1$ está //presente// em um vértice $v\in V$ se alguma aresta que incide nele está colorida com essa cor. Caso contrário, dizemos que essa cor está //ausente// nesse vértice. Como $\Delta(G)+1$ cores estão sendo utilizadas, em todo vértice há uma cor ausente. Assim, definimos um //leque// sobre o vértice $x$ (fixado como extremidade da aresta $xy$ removida) como uma ordenação $(xy_1,xy_2,\dots,xy_k)$ de arestas nele incidentes tal que: Para descrevermos uma coloração para o grafo $G$, faremos uso de certas notações auxiliares. Primeiro, diremos que uma cor $1 \leq i\leq \Delta(G)+1$ está //presente// em um vértice $v\in V$ se alguma aresta que incide nele está colorida com essa cor. Caso contrário, dizemos que essa cor está //ausente// nesse vértice. Como $\Delta(G)+1$ cores estão sendo utilizadas, em todo vértice há uma cor ausente. Assim, definimos um //leque// sobre o vértice $x$ (fixado como extremidade da aresta $xy$ removida) como uma ordenação $(xy_1,xy_2,\dots,xy_k)$ de arestas nele incidentes tal que:
Linha 38: Linha 49:
   * Se $x$ e $y_{i-1}$ não pertencem a mesma componente conexa de $H$, faremos a troca das cores $1$ e $i$ na componente em que se encontra $y_{i-1}$, observando que isso determina de fato uma coloração de arestas. Nesse novo cenário, a cor $1$ está ausente no vértice $y_{i-1}$ (se é que já não estava ausente antes, inclusive), bem como continua ausente no vértice $x$. Agora, $(xy_1,xy_2,\dots,xy_{i-1})$ é um leque com respeito a essa nova coloração. Podemos então colorir $xy_{i-1}$ com a cor $1$ e $xy_j$ com a cor $j+1$ para todo $1 \leq j \leq i-2$. Em particular, a aresta $xy$ está colorida, finalizando o processo indutivo nesse caso.   * Se $x$ e $y_{i-1}$ não pertencem a mesma componente conexa de $H$, faremos a troca das cores $1$ e $i$ na componente em que se encontra $y_{i-1}$, observando que isso determina de fato uma coloração de arestas. Nesse novo cenário, a cor $1$ está ausente no vértice $y_{i-1}$ (se é que já não estava ausente antes, inclusive), bem como continua ausente no vértice $x$. Agora, $(xy_1,xy_2,\dots,xy_{i-1})$ é um leque com respeito a essa nova coloração. Podemos então colorir $xy_{i-1}$ com a cor $1$ e $xy_j$ com a cor $j+1$ para todo $1 \leq j \leq i-2$. Em particular, a aresta $xy$ está colorida, finalizando o processo indutivo nesse caso.
   * Se $x$ e $y_{i-1}$ pertencem à mesma componente conexa de $H$, que é um caminho, esses vértices são suas extremidades. Assim, como a cor $i$ é ausente em $y_k$, o vértice $y_k$ está em uma componente conexa distinta da de $x$. Como antes, então, trocaremos as cores $1$ e $i$ nas arestas dessa componente. Isso define uma nova coloração de arestas em que a cor $1$ se torna ausente em $y_k$, embora $1$ continue ausente em $x$ e $i$ continue ausente em $y_{i-1}$ - visto que a coloração não foi mudada na componente de $H$ que contém esses vértices. Com respeito a essa nova coloração, a sequência $(xy_1,xy_2,\dots,xy_k)$ é também um leque, mas agora é possível colorir a aresta $xy_k$ com a cor $1$ e cada aresta $xy_j$ com a cor $j+1$, para todo $1 \leq j \leq k-2$. Em particular, a aresta $xy = xy_1$ está colorida, finalizando o processo indutivo nesse caso.   * Se $x$ e $y_{i-1}$ pertencem à mesma componente conexa de $H$, que é um caminho, esses vértices são suas extremidades. Assim, como a cor $i$ é ausente em $y_k$, o vértice $y_k$ está em uma componente conexa distinta da de $x$. Como antes, então, trocaremos as cores $1$ e $i$ nas arestas dessa componente. Isso define uma nova coloração de arestas em que a cor $1$ se torna ausente em $y_k$, embora $1$ continue ausente em $x$ e $i$ continue ausente em $y_{i-1}$ - visto que a coloração não foi mudada na componente de $H$ que contém esses vértices. Com respeito a essa nova coloração, a sequência $(xy_1,xy_2,\dots,xy_k)$ é também um leque, mas agora é possível colorir a aresta $xy_k$ com a cor $1$ e cada aresta $xy_j$ com a cor $j+1$, para todo $1 \leq j \leq k-2$. Em particular, a aresta $xy = xy_1$ está colorida, finalizando o processo indutivo nesse caso.
 +
 <wrap right>$\square$</wrap> <wrap right>$\square$</wrap>
-   +</WRAP>
      
 +----
  
 +O teorema de Vizing divide os grafos finitos em duas classes de acordo com seu índice cromático; grafos que satisfazem $\chi '=\Delta$ são chamados (imaginativamente) de //classe// $1$, aqueles com $\chi ' = \Delta + 1$ são de //classe// $2$. Não há um bom teorema de caracterização que nos permita diferenciar essas classes, porque nenhum 'certificado' facilmente verificável é conhecido para um grafo como //classe// $2$.
  
 +Grafos regulares de grande ordem par e grande grau são classe $1$:
 +
 +<WRAP round box 100%>
 +=== Teorema (Csaba, Kuhn, Lo, Osthus, Treglown) ===
 +//Existe um $n_0 \in \mathbb{N}$ tal que, para todo $n \geq n_0$ e $d \geq n/2$, todo grafo $d$-regular $G$ de ordem $n$ satisfaz $\chi '(G) = \Delta (G)$.//
 +</WRAP>
 +
 +----
 +
 +<WRAP round info 100%>
 +=== Referências ===
 +  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 127-129. Acesso em 21/06/2023.
 +
 +</WRAP>
  • grafos/colarestas.1686591829.txt.gz
  • Última modificação: 2023/06/12 14:43
  • por piva