Teoria dos Grafos: Conceitos Básicos
1) Rotulação e Representação dos Grafos:
Os grafos são utilizados para a modelagem e representação de problemas. Os grafos são um conjuntos de vértices que podem ser interligados por arestas. Cada um desses elementos podem possuir um significado de acordo com o problema descrito.
O rótulo dado no título é interessante e necessário. A teoria dos grafos pode ser uma ferramenta para modelar uma fórmula da química orgânica por exemplo. Os hidrocarbonetos:
2) Conceitos Básicos sobre Grafos:
Os grafos são um conjunto de vértices e arestas que conectam cada vértice. Os vértices podem ser chamados de nós.
O modo com que o grafo se apresenta em sua forma não é significativo, podemos representar o mesmo grafo de formas diferentes. O que realmente importa são o conjunto de vértices que o mesmo possui e o conjunto de arestas que interligam esses nós.
Um grafo possui um conjunto de Vértices V e um conjunto de Arestas (ou arcos) A.
Um exemplo demonstra um grafo com 4 vértices e 5 arestas, no qual são representadas de formas diferentes, porém são o mesmo grafo:
Definição 1) Loop : É quando uma aresta tem ponto inicial em um vértice Vn e tem seu ponto final no mesmo vértice Vn. Como exemplo vemos o grafo abaixo:
3) Definição de Grafos:
Assim como visto nos exemplos acima, temos os conjuntos (V, A, g). A função g ainda não foi vista nos exemplos acima, ainda mais que muitos autores não utilizam em suas respectivas literaturas, simplificando então o grafo como (V,A), uma vez que os arcos ligam diretamente os vértices do conjunto V.
Definição 2) Vértices Adjacentes: Sejam o arco e e os vértices v e w. Se o arco e interligar os vértices v e w, representamos da forma: e {v,w} ou e {w, v}. Os vértices conectados pelo arco e, são chamados então de vértices adjacente, portanto v e w no caso, são vértices adjacentes.