Teoria dos grafos
Pontos e linhas entre eles: um grafo não é mais do que isso. No entanto, a mesma figura descreve um mapa de estradas, uma rede de amigos, uma molécula e a internet, e as perguntas que se podem fazer sobre ela, desde quantas cores são precisas até se é possível percorrê-la num só traço, mantêm os matemáticos ocupados desde 1736.
Vértices e arestas
Um grafo tem vértices, também chamados nós, e arestas, cada uma das quais une dois vértices. Não importa onde os vértices são desenhados, apenas que pares estão unidos, por isso o mesmo grafo pode parecer muito diferente no papel. Os grafos do laboratório são simples: nenhuma aresta vai de um vértice para si próprio e entre dois vértices há no máximo uma aresta. Com n vértices pode haver no máximo n(n − 1) / 2 arestas; um grafo que as tem todas chama-se completo, e K5 é o grafo completo com cinco vértices.
Graus e o lema do aperto de mão
O grau de um vértice é o número de arestas que nele incidem. Somando todos os graus obtém-se exatamente o dobro do número de arestas, porque cada aresta tem duas extremidades e é contada uma vez em cada uma. É o lema do aperto de mão: em qualquer grupo, os apertos de mão contados pessoa a pessoa somam o dobro do número de apertos de mão. Isto também significa que o número de vértices com grau ímpar é sempre par. Um grafo em que todos os vértices têm o mesmo grau k chama-se k-regular.
Grafos conexos, árvores e ciclos
Um grafo é conexo quando se pode ir de qualquer vértice a qualquer outro seguindo as arestas; caso contrário, divide-se em partes, chamadas componentes. Um ciclo é uma volta que regressa ao ponto de partida sem passar duas vezes pelo mesmo vértice, e o comprimento do mais curto é a cintura. Um grafo conexo sem ciclos é uma árvore, e uma árvore com n vértices tem sempre exatamente n − 1 arestas: com uma a menos divide-se, com uma a mais tem um ciclo. Todo o grafo conexo contém uma árvore geradora, uma árvore que chega a todos os vértices usando apenas algumas das arestas.
Grafos bipartidos e coloração
Pinte os vértices de modo que nenhuma aresta una dois vértices da mesma cor. O menor número de cores com que isso é possível é o número cromático. Uma só cor basta apenas quando não há arestas. Duas cores bastam exatamente quando o grafo é bipartido: os seus vértices dividem-se em dois lados e todas as arestas vão de um ao outro. Dénes Kőnig mostrou em 1936 que isto equivale a não ter ciclos de comprimento ímpar, porque um ciclo ímpar não pode alternar entre duas cores. Para três ou mais cores não se conhece nenhum teste tão simples: decidir se três cores bastam é um problema NP-completo, por isso os programas fazem uma pesquisa, tal como o laboratório.
Um exemplo: o grafo de Petersen
Pegue num pentágono A–B–C–D–E e numa estrela de cinco pontas F–H–J–G–I dentro dele, e una cada canto do pentágono a uma ponta da estrela: A–F, B–G, C–H, D–I e E–J. É o grafo de Petersen, com 10 vértices e 15 arestas. Todos os vértices têm grau 3, por isso os graus somam 30, o dobro de 15. O seu ciclo mais curto tem comprimento 5, por isso não tem triângulos, mas o pentágono é um ciclo ímpar, por isso não é bipartido e precisa de 3 cores. Quaisquer dois vértices estão no máximo a 2 arestas de distância, por isso o seu diâmetro é 2. Os dez graus são todos ímpares, por isso não tem trilho euleriano, e não pode ser desenhado sem cruzamentos.
Caminhos eulerianos e as pontes de Königsberg
A cidade de Königsberg tinha sete pontes que uniam quatro porções de terra, e as pessoas perguntavam-se se seria possível atravessar cada ponte exatamente uma vez. Em 1736, Leonhard Euler mostrou que não, e assim nasceu a teoria dos grafos. Sempre que um passeio passa por uma porção de terra usa duas pontes, por isso só o início e o fim podem ter um número ímpar delas, e as quatro porções de terra de Königsberg tinham todas um número ímpar. Um trilho que usa cada aresta uma vez chama-se hoje caminho euleriano, ou circuito euleriano quando termina onde começou. Carl Hierholzer provou em 1873 que a condição também é suficiente: se todas as arestas estão numa só parte e no máximo dois graus são ímpares, o trilho existe, e o seu método de ir juntando voltas ainda hoje o encontra.
Distância, diâmetro e complemento
A distância entre dois vértices é o menor número de arestas de um caminho entre eles, e o diâmetro é a maior distância no grafo; num grafo que não é conexo, é infinito. As redes sociais têm diâmetros pequenos, a ideia por trás dos seis graus de separação. O complemento de um grafo tem os mesmos vértices e une exatamente os pares que não estavam unidos. De um grafo e do seu complemento, pelo menos um é sempre conexo.
Explore
O laboratório abre com o grafo de Petersen colorido em três cores. Clique em Graus e verifique o lema do aperto de mão, clique em Bipartido para ver um ciclo ímpar e depois carregue o cubo e veja os dois lados aparecerem. Carregue a casa e clique em Trilho euleriano para ver onde o traço tem de começar. Desenhe o seu próprio grafo e acrescente uma aresta de cada vez: veja o ciclo mais curto encolher, o diâmetro descer e o número cromático subir quando entra a última aresta de um K4.
Perguntas frequentes
Qual é a diferença entre um caminho, um trilho e um passeio?
Um passeio é qualquer sequência de vértices unidos por arestas e pode repetir ambos. Um trilho pode repetir vértices, mas não arestas, e é por isso que um trilho euleriano pode passar várias vezes pelo mesmo vértice. Um caminho não repete nenhum dos dois.
O que é o teorema das quatro cores?
Diz que qualquer grafo que se possa desenhar no papel sem arestas a cruzarem-se pode ser colorido com no máximo quatro cores, por isso nenhum mapa precisa de mais de quatro. Foi provado em 1976 por Kenneth Appel e Wolfgang Haken com a ajuda de um computador, o primeiro grande teorema provado dessa forma.
O que é um ciclo hamiltoniano?
Um ciclo que visita cada vértice exatamente uma vez, em vez de cada aresta. Parece a pergunta de Euler, mas não se conhece nenhum teste simples: decidir se um grafo tem um é um problema NP-completo. O grafo de Petersen tem um caminho hamiltoniano, mas não um ciclo hamiltoniano.
Onde é usada a teoria dos grafos?
Os planeadores de rotas pesquisam grafos de estradas, os motores de busca ordenam as páginas web pelas suas ligações, os compiladores colorem grafos para partilhar os registos do processador, os horários evitam sobreposições colorindo um grafo de conflitos, os químicos contam moléculas como grafos, e as redes de computadores, as redes elétricas e as redes de amigos são estudadas como grafos.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o laboratório de teoria dos grafos