Grafos

Conceitos Básicos

   Grafos são estruturas matemática que permitem codificar relacionamentos entre pares de objetos. Os objetos são os nós do grafo enquanto os relacionamentos são as arestas. Não necessariamente todos os objetos possuirão aresta apenas quando ocorrer um relacionamento.

Relacionamento O relacionamento de ser adotado a vários tipos de aplicações. Em um rede social relacionamento entre pessoas. Em um estação de metro relacionamento entre trem e estação. Relacionamento entre estradas e municípios, generalizando, lugares. E assim vai ...

Grafos podem ser dirigidos ( direcionados) : Isso quer dizer há apenas uma direção no relacionamento. Existindo assim pares ordenados. Mesmo que ambos sejam o mesmo vértice ( self-loop ).

Grafos podem ser não dirigidos ( não direcionados ): Onde não há sentido na aresta  . As arestas podem ser seguidas em qualquer direção. Podemos pensar num grafo não dirigido com um grafo dirigido com aresta de sentido duplo. As arestas são pares não ordenados de vértices. Self-loops não são permitidos.

Se (u,v) é uma aresta no grafo, então dizemos que v é adjacente a u. Alternativamente, que v é vizinha de u. ( u, v ) significa que a aresta sai de u e entra em v. Em grafos não dirigidos nós teremos uma simetria: ( v,u ) <=>( u,v ) Já em dirigidos não há essa simetria.

Grau de um vértice é o número de arestas que incidem nele. gr( v1 ) = 2 Já em grafos dirigidos, o grau de um vértice é  o número de arestas que saem do vértice mais o número de aresta que chegam nele. Poderiamos subdividem graus de entrada e grau de saída. Contudo self-loop não é permitido para grafos que não sejam dirigidos.  

Um caminho de um vértice x a um vértice y é uma sequência de vértices em que, para cada vértice, primeiro ao penúltimo, há uma aresta ligando ele até o próximo na sequência. ( v1 , v2, v3 , v5) ( v4, v4, v5) O comprimento de um caminho é o número de arestas nele. compr( v1, v2, v3 , v4) Um ciclo acontece quando, a partir de um determinado vértice, pudermos percorrer algum caminho que nos leve a esse mesmo vértice. Em grafos dirigidos, o caminho deve conter pelo menos uma aresta. Em grafos dirigidos, o caminho deve conter pelo menos uma arestas. O seja pelo menos um self-loop.   Em grafos não dirigidos, um ciclo deve conter pelo menos 3 arestas. Grafos em que há ao menos um ciclo são chamados de cíclicos. Grafos em que não há ciclo é acíclicos.

Um grafo não direcionado é conexo ( conectado) se cada par de vértices nele estivar conectado por um caminho. Caso pelo menos um dos pares não esteja conectado então é desconexo. No caso do direcionado: Fortemente conexo - existirá um caminho entre qualquer par de vértices no grafo. Conexo - para qualquer par de vértice existirá um caminho que vai ou um caminho que volta. Fracamente conexo -  basicamente não há caminho de volta para o vértice origem. Caso as arestas do grafo sejam substituídas por arestas não direcionada então tornará um grafo conexo. Grafos podem ser ponderados - Existem valores associados a aresta. Seu significado dependerá da modelagem.

Por fim, árvore também um grafo acíclico, conexo e não dirigido. fonte: https://youtu.be/MC0u4f334mI?list=PLxI8Can9yAHf8k8LrUePyj0y3lLpigGcl