Neste capítulo tem o objetivo de introduzir alguns conceitos básicos da Teoria
dos Grafos, tais como grafos simples e completo, grafo conexo, grau do vértice,
grafos Eulerianos, laços, subgrafos, etc.
A importância do esclarecimento destes conceitos ao leitor, é ele compreender os grafos das turmas de Analise e Desenvolvimento de Sistemas e Ciência da Computação, gerados a partir dos dados do questionário entregue aos alunos.
A utilização da Teoria dos Grafos é importante, pois, para Bogart (2013), podemos usar grafos para representar muitas situações comuns e descrever naturalmente muitos algoritmos. Os grafos também são um ponto de encontro ideal para desenvolver um conhecimento mais profundo da prova por indução, especialmente da indução forte. Redes de comunicação, fluxo de transporte aéreo, transporte térreo e na área da saúde, são algumas áreas que utilizam os grafos para soluções de problemas.
O grafo é definido por um conjunto de vértices e arestas, que é representado por G(V,A), onde V é a vértice ou nó, A é aresta e G é o conjunto. Podemos representá-los visualmente ou por extenso. As arestas de um grafo podem apresentar pesos, que representa o custo para chegar de um vértice X para Y. Como exemplo a Figura 4, as vértices B, C, e D têm um grau 3 e a vértice A com grau 5. Abaixo vemos um exemplo de grafo, contendo 4 arestas e 4 vértices:
Grafos contém propriedades particulares, tais propriedades definem o comportamento do grafo e diz qual grupo ele pertence. Abaixo segue tais propriedades:
Grau: Toda vértice apresenta um grau, que é definido pela quantidade de arestas, ligações, com outros vértices ou com o ele Na figura 2, os vértices 1 e 3 têm grau 3, o 2 vértice tem grau 5, o vértice 4 tem o grau 1, e o vértice 5 tem grau 0. Em um grafo direcionado o grau de uma vértice y é medido pela quantidade de arestas que sai do vértice origem (y) para a vértice destino (x). Na Figura abaixo temos como exemplo um grafo direcionado com 4 vértices e 4 arestas, os vértices a e d têm grau 1, o vértice b tem grau 2 e o vértice c tem grau 0. (Feofiloff, 2011)
Laços: Um laço ou self-loop, em inglês, é uma aresta ligada na mesma vértice. Como na Figura 2, onde a vértice e conecta a lá mesma. g(a3)=2-2, Os grafos que serão analisados nesta pesquisa não contem laços,
Arestas Paralelas: Arestas paralelas são arestas com o mesmo vértice origem e destino, como no exemplo as arestas a1 e a2, na Figura 2, mas o a1 e a4 não são paralelos, pois um dos seus extremos, origem e destino, não são equivalentes.
Caminho: Um caminho de um grafo é determinado por um sequencia de arestas para chegar de um vértice x para y. No grafo da figura 4, um caminho do vértice A para o vértice F consiste na sequência A,1,B,2,C,5,E,6,F ou A,1,B,3,D,4,E,6,F
Adjacência: Adjacência é quando dois vértices estão ligados a uma aresta, na Figura 4, o vértice C é adjacente do E, mas o vértice C não é adjacente F, pois não uma aresta entre os vértices. Um conjunto de vizinhos de um vértice consiste de todos os vértices ligados a ele. No grafo da figura 4, os vizinhos de C é B e E.
Grafo simples: Um grafo é considerado simples quando na sua estrutura não contem laços e arestas paralelas.
Grafo orientado (DIGRAFO):Um grafo direcionado (digrafo) é uma tripla ordenada (N, A, g) onde :
Grafo completo: Um grafo é considerado como completo quando ele seja simples e que cada nó do grafo estiver conectado com os restantes nós do grafo, ou seja, o nó n1 esta conectado á todos os nós, nn, do grafo e vice-versa.
A importância do esclarecimento destes conceitos ao leitor, é ele compreender os grafos das turmas de Analise e Desenvolvimento de Sistemas e Ciência da Computação, gerados a partir dos dados do questionário entregue aos alunos.
A utilização da Teoria dos Grafos é importante, pois, para Bogart (2013), podemos usar grafos para representar muitas situações comuns e descrever naturalmente muitos algoritmos. Os grafos também são um ponto de encontro ideal para desenvolver um conhecimento mais profundo da prova por indução, especialmente da indução forte. Redes de comunicação, fluxo de transporte aéreo, transporte térreo e na área da saúde, são algumas áreas que utilizam os grafos para soluções de problemas.
O grafo é definido por um conjunto de vértices e arestas, que é representado por G(V,A), onde V é a vértice ou nó, A é aresta e G é o conjunto. Podemos representá-los visualmente ou por extenso. As arestas de um grafo podem apresentar pesos, que representa o custo para chegar de um vértice X para Y. Como exemplo a Figura 4, as vértices B, C, e D têm um grau 3 e a vértice A com grau 5. Abaixo vemos um exemplo de grafo, contendo 4 arestas e 4 vértices:
Grafos contém propriedades particulares, tais propriedades definem o comportamento do grafo e diz qual grupo ele pertence. Abaixo segue tais propriedades:
Grau: Toda vértice apresenta um grau, que é definido pela quantidade de arestas, ligações, com outros vértices ou com o ele Na figura 2, os vértices 1 e 3 têm grau 3, o 2 vértice tem grau 5, o vértice 4 tem o grau 1, e o vértice 5 tem grau 0. Em um grafo direcionado o grau de uma vértice y é medido pela quantidade de arestas que sai do vértice origem (y) para a vértice destino (x). Na Figura abaixo temos como exemplo um grafo direcionado com 4 vértices e 4 arestas, os vértices a e d têm grau 1, o vértice b tem grau 2 e o vértice c tem grau 0. (Feofiloff, 2011)
Laços: Um laço ou self-loop, em inglês, é uma aresta ligada na mesma vértice. Como na Figura 2, onde a vértice e conecta a lá mesma. g(a3)=2-2, Os grafos que serão analisados nesta pesquisa não contem laços,
Arestas Paralelas: Arestas paralelas são arestas com o mesmo vértice origem e destino, como no exemplo as arestas a1 e a2, na Figura 2, mas o a1 e a4 não são paralelos, pois um dos seus extremos, origem e destino, não são equivalentes.
Caminho: Um caminho de um grafo é determinado por um sequencia de arestas para chegar de um vértice x para y. No grafo da figura 4, um caminho do vértice A para o vértice F consiste na sequência A,1,B,2,C,5,E,6,F ou A,1,B,3,D,4,E,6,F
Adjacência: Adjacência é quando dois vértices estão ligados a uma aresta, na Figura 4, o vértice C é adjacente do E, mas o vértice C não é adjacente F, pois não uma aresta entre os vértices. Um conjunto de vizinhos de um vértice consiste de todos os vértices ligados a ele. No grafo da figura 4, os vizinhos de C é B e E.
Grafo simples: Um grafo é considerado simples quando na sua estrutura não contem laços e arestas paralelas.
Grafo orientado (DIGRAFO):Um grafo direcionado (digrafo) é uma tripla ordenada (N, A, g) onde :
N = um conjunto de vértices
A = um conjunto de arestas
g = uma função que associe a cada aresta a um par ordenado (x, y) de vértices, onde x é o ponto inicial e y é o ponto final de a. (GERSTING,J.L. , 1999)
Grafo completo: Um grafo é considerado como completo quando ele seja simples e que cada nó do grafo estiver conectado com os restantes nós do grafo, ou seja, o nó n1 esta conectado á todos os nós, nn, do grafo e vice-versa.
Nenhum comentário:
Postar um comentário