Teoria de Grafos
Matemática Aplicada às Ciências Socias, 11º ano
Teoria de Grafos
Origem:
Leonard Euler
Pontes de Königsberg
Teoria de Grafos
A aplicação desta teoria não é utilizada especificamente na Matemática.
Abrange também áreas diversas, como, por exemplo, o planeamento de uma rede de comunicações viária, projetos de arquitetura, desenho de circuitos eletrónicos, resolução de problemas inerentes às telecomunicações, distribuição de produtos e controlo de tráfego urbano.
Um grafo constitui o modelo matemático ideal para o estudo das relações entre objetos discretos de qualquer tipo .
Teoria de Grafos
A seguinte secção de um mapa de estradas
Exemplos :
ou a seguinte secção de uma rede eléctrica
podem ser ambas representadas por meio de pontos e segmentos de reta do seguinte modo:
Teoria de Grafos
Assim
Um grafo é uma representação esquemática constituída por conjuntos finitos de pontos, a que chamamos vértices, e por segmentos que unem os vértices, a que chamamos arestas.
Linguagem e notação da teoria dos grafos
Teoria de Grafos
Por exemplo:
Teoria de Grafos
Grafo conexo é um grafo no qual existe sempre uma sequência de arestas a unir quaisquer dois dos seus vértices.
Grafo conexo
Grafo não conexo
Teoria de Grafos
Grafo simples é um grafo que não tem arestas paralelas nem lacetes. Se tiver algum destes elementos, chama- se multigrafo.
Grafo simples
Multigrafo
Teoria de Grafos
Grafo completo é um grafo em que qualquer par de vértices está ligado por uma aresta.
Grafo completo
Grafo não completo
Teoria de Grafos
Grau, ou valência, de um vértice é o número de arestas que nele incidem.
grau 2
grau 3
grau 1
grau 3
grau 3
grau 0
Teoria de Grafos
Grafo regular é um grafo em que todos os vértices têm o mesmo grau.
grau 4
grau 4
grau 4
grau 4
grau 4
Teoria de Grafos
Grafo orientado, ou dígrafo, é um grafo cujas arestas têm sentidos definidos.
Teoria de Grafos
Bibliografia:
http://www.mat.uc.pt/~picado/ediscretas/2013/apontamentos/cap2.pdf
PPT adaptado do Manual