grafos:tiposgrafos

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

grafos:tiposgrafos [2023/01/24 16:58] – edição externa 127.0.0.1grafos:tiposgrafos [2023/08/10 14:46] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
 ===== Tipos básicos de grafos ===== ===== Tipos básicos de grafos =====
  
-Há vários tipos de grafos, vamos enumerar alguns deles e apresentar algumas propriedades, alguns, inclusive, já tiveram, ou terão sua própria documentação com uma descrição mais abrangente. Vamos começar pelos **Grafos Triviais.**+Há vários tipos de grafos, vamos enumerar alguns deles e apresentar algumas propriedades. Alguns, inclusive, já tiveram, ou terão sua própria documentação com uma descrição mais abrangente. Vamos começar pelos **Grafos Triviais.**
  
 ====Grafos Triviais==== ====Grafos Triviais====
Linha 7: Linha 7:
 <WRAP round box 90%> <WRAP round box 90%>
 === Definição === === Definição ===
-//Um grafo trivial é um grafo no qual $G = (V ; ∅)$, ou seja, é um grafo que possui $n$ vértices, podendo ser representado por conjunto de $n$ pontos no plano, sem quaisquer arestas.//+//Um grafo trivial é um grafo no qual $G = (V ; \emptyset)$, ou seja, é um grafo que possui $n$ vértices, podendo ser representado por conjunto de $n$ pontos no plano, sem quaisquer arestas.//
 </WRAP> </WRAP>
  
-Assim sendo, um grafo de **ordem 0 ou 1** é chamado **grafo trivial**. Geralmente, por definição, tratamos os grafos triviais de forma despreziva, pois formam contra-exemplos bobos e se tornam um incomômdo, mas não se engane, em algumas situações, para iniciar uma indução,por exemplo, grafos triviais podem ser muito úteis. O grafo $G$ vazio pode ser representado somente por $G = Ø$.+Assim sendo, um grafo de **ordem $0$ ou $1$** é chamado **grafo trivial**. Geralmente, por definição, tratamos os grafos triviais de forma despreziva, pois formam contra-exemplos bobos e se tornam um incomômdo, mas não se engane, em algumas situações, para iniciar uma indução,por exemplo, grafos triviais podem ser muito úteis. O grafo $G$ vazio pode ser representado somente por $G = \emptyset$.
  
 ==== Grafos Simples ==== ==== Grafos Simples ====
Linha 19: Linha 19:
  
 === Definição=== === Definição===
-Um grafo (simples) $G$ consiste de um conjunto finito e não vazio $V(G)$ de objetos chamados vértices, juntamente com um conjunto $A(G)$ de pares não ordenados de vértices; os elementos de $A(G)$ são chamados de arestas. Podemos representá-lo por $G = (V ; A)$, onde $V = V (G)$ e $A = A(G)$.+//Um grafo (simples) $G$ consiste de um conjunto finito e não vazio $V(G)$ de objetos chamados vértices, juntamente com um conjunto $A(G)$ de pares não ordenados de vértices; os elementos de $A(G)$ são chamados de arestas. Podemos representá-lo por $G = (V ; A)$, onde $V = V (G)$ e $A = A(G)$.//
 </WRAP> </WRAP>
  
-Assim sendo, um grafo simples é um grafo não direcionado, não ponderado, que não possuem laços nem mais de uma aresta ligando dois vértices,isto é, sem arestas “paralelas”. Assim, um grafo simples é um grafo que não possui arestas múltiplas. Como ,por exemplo, o grafo abaixo:+Assim sendo, um grafo simples é um grafo não direcionado, não ponderado, que não possuem [[.loopsmultigraph |laços]] nem mais de uma aresta ligando dois vértices,isto é, sem arestas “paralelas”. Assim, um grafo simples é um grafo que não possui arestas múltiplas. Como ,por exemplo, o grafo abaixo:
  
 {{ :grafos:grafo_1.png?250 |}} {{ :grafos:grafo_1.png?250 |}}
Linha 33: Linha 33:
  
 === Definição=== === Definição===
-Um grafo direcionado $G(V, A)$ é constituído por um conjunto $V = \{v_1, v_2, …, v_n\}$ não vazio de vértices, e um conjunto $A = \{a_1, a_2, …, a_n\}$ de arestas, e uma aplicação que associa cada arestas a um par ordenado de vértices.+//Um grafo direcionado $G(V, A)$ é constituído por um conjunto $V = \{v_1, v_2, …, v_n\}$ não vazio de vértices, e um conjunto $A = \{a_1, a_2, …, a_n\}$ de arestas, e uma aplicação que associa cada arestas a um par ordenado de vértices.//
 </WRAP> </WRAP>
  
Linha 41: Linha 41:
  
 <WRAP tip round box 100%> <WRAP tip round box 100%>
-=== Nota: ===+=== Nota ===
 Quando um grafo possui mais de uma aresta interligando os mesmo dois vértices diz-se que este grafo possui arestas múltiplas(ou arestas paralelas). Ele é chamado de multigrafo ou grafo múltiplo. O grafo acima, observe, além de ser orientado, ele pode ser chamado de **multigrafo** também. Mas cuidado, nem todo grafo orientado pode ser dito multigrafo. Quando um grafo possui mais de uma aresta interligando os mesmo dois vértices diz-se que este grafo possui arestas múltiplas(ou arestas paralelas). Ele é chamado de multigrafo ou grafo múltiplo. O grafo acima, observe, além de ser orientado, ele pode ser chamado de **multigrafo** também. Mas cuidado, nem todo grafo orientado pode ser dito multigrafo.
  
-Em um multigrafo, se houver uma aresta $e$ de um grafo $G$ que possui o mesmo vértice como extremos, ou seja, $e = {x,x}$, então é dito que este grafo possui um **laço**. Observe que no exemplo a seguir o grafo possui um laço localizado no vértice (1):+Em um multigrafo, se houver uma aresta $e$ de um grafo $G$ que possui o mesmo vértice como extremos, ou seja, $e = \{x,x\}$, então é dito que este grafo possui um **laço**. Observe que no exemplo a seguir o grafo possui um laço localizado no vértice $(1)$:
  
 {{:grafos:graphs_7_.png?150 |}} {{:grafos:graphs_7_.png?150 |}}
Linha 75: Linha 75:
 <WRAP round box 80%> <WRAP round box 80%>
 === Definição === === Definição ===
-Um grafo é dito **conexo** se existir pelo menos um caminho entre cada par de vértices do grafo. Caso contrário, o grafo é chamado de **desconexo**.+//Um grafo é dito **conexo** se existir pelo menos um caminho entre cada par de vértices do grafo. Caso contrário, o grafo é chamado de **desconexo**.//
 </WRAP> </WRAP>
  
Linha 86: Linha 86:
 {{:grafos:graph_14_.png?300|}} {{:grafos:graph_14_.png?300|}}
  
 +
 +----
 <WRAP round info 100%> <WRAP round info 100%>
 === Referências === === Referências ===
  • grafos/tiposgrafos.1674590301.txt.gz
  • Última modificação: 2023/01/24 16:58
  • por 127.0.0.1