GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Mat Disc - Grafos

Raiza Wunsch Matemática 1º ano English 63 cards

Cards in this deck (63)

  1. 1Grafo Simplesum grafo no qual cada aresta conecta dois vértices diferentes e duas arestas nunca conectam o mesmo par de vértices.
  2. 2Um grafo simples é uma relação binária em V(G): (reflexão, simetria e transitividade)simétrica e irreflexível.
  3. 3Multigrafosos grafos que podem ter arestas múltiplas conectando os mesmos vértices
  4. 4quando existem m arestas diferentes associadas ao mesmo par não ordenado de vertices {u, v}, dizemos também que {u, v} éuma aresta de multiplicidade m.
  5. 5Laçosarestas que conectam um vértice a si mesmo
  6. 6são, algumas vezes, chamados de pseudografosgrafos que incluem laços, e possivelmente arestas múltiplas que conectam o mesmo par de vertices
  7. 7um grafo orientado (ou dígrafo) (V, E), consiste emum conjunto não vazio de vertices V e um conjunto de arestas orientadas E ('edges'). Cada aresta orientada está associada a um par ordenado de vértices. É dito que aresta orientada associada ao par ordenado (u, v) COMEÇA em u e TERMINA em v.
  8. 8Grafo orientado simplesQuando um grafo orientado não tem laços nem arestas orientadas múltiplas
  9. 9multigrafos orientadosOs grafos orientados que podem ter arestas orientadas múltiplas de um vértice para um segundo vértice (possivelmente o mesmo)
  10. 10Quando existirem m arestas orientadas, cada uma delas associadas a um par ordenado de vertices (u, v), dizemos que (u, v) éuma aresta de multiplicdade m
  11. 11Um grafo com tanto arestas orientadas quanto não orientadas é chamado degrafo misto
  12. 12Três questões-chave que podem nos ajudar a entender a estrutura de um grafo independentemente de qual terminoliogia está sendo usada:- Tem arestas orientadas?
    - Tem arestas múltiplas?
    - Tem laços?
  13. 13Passeio, Caminho, Trilha, Circuito e CicloPasseio: Sequência de vértices vizinhos. Permite repetição de vértices e arestas.
    Caminho: Passeio que não permite repetição de vértices (exceto início/fim no caso de ciclos).
    Trilha: Passeio que não permite repetição de arestas (mas permite repetição de vértices).
    Circuito: Trilha fechada. Termina onde começa.
    Ciclo: Caminho fechado. Termina onde começa.
  14. 14Trilha ou Circuito usando todas as arestas:Euleriano
  15. 15Caminho ou Ciclo usando todos os vértices:Hamiltoniano
  16. 16Um grafo simples que contém muitas arestas é ditodenso
  17. 17Um grafo não orientado é dito conexo seexistir um caminho entre qualquer par de vértices distintos no grafo.
  18. 18Um grafo orientado é fortemente conexo seexistir um caminho de a a b e de b a a sempre que a e b forem vértices do grafo. Ou seja, se existir uma sequência de arestas orientadas de qualquer vértice no grafo para qualquer outro vértice.
  19. 19Um grafo orientado é fracamente conexo seexistir um caminho entre quaisquer dois vértices no grafo não orientado subjacente.
  20. 20- Dois vertices u e v em um grafo não orientado G são ditos adjacentes (ou vizinhos) em G seu e v são extremidades de uma aresta de G. Diz-se também que a aresta CONECTA u e v. Os vertices u e v são chamados de EXTREMIDADES de uma aresta associada a {u, v}.
  21. 21- O GRAU de um vértice v em um grafo não orientado, indicado por gr(v), éo número de arestas incidents a ele, exceto que um laço em um vértice contribui duas vezes ao grau daquele vértice.
  22. 22- Um vértice de grau zero é ditoisolado
  23. 23- Um vértice é pendente se e somente seele tem grau 1
  24. 24- Teorema do Aperto de Mãos:Seja G = (V, E) um grafo não orientado com m arestas. Então
    2m = Σgr(v).
    "A soma dos graus de todos os vértices de um grafo não orientado é igual ao dobro do número de arestas no grafo."
    Isso significa que cada aresta contribui com 2 para a soma dos graus dos vertices, pois uma aresta é incidente a exatamente dois vertices.
  25. 25- Do teorema do aperto de mãos, segue que em grafo não orientado tem um número ____ de vertices de grau ____- Um grafo não orientado tem um número par de vertices de grau ímpar
  26. 26- Quando (u, v) for uma aresta em um grafo G com arestas orientadas, dizemos queu é ADJACENTE PARA v e v é ADJACENTE A PARTIR de u. O vértice u é dito VÉRTICE INICIAL de (u, v) e v é dito VÉRTICE FINAL ou TERMINAL de (u, v). Em um laço, os vértices inicial e final são os mesmos.
  27. 27- Em um grafo com arestas orientadas, o GRAU DE ENTRADA de um vértice v, indicado por gr⁻(v), éo número de arestas que tem v como seu vértice FINAL.
    (observe que um laço em um vértice contribui 1 tanto para o grau de entrada quanto para o grau de saída)
  28. 28- Em um grafo com arestas orientadas, o GRAU DE SAÍDA de v, indicado por gr⁺(v), éo número de arestas que tem v como seu vértice INICIAL.
    (observe que um laço em um vértice contribui 1 tanto para o grau de entrada quanto para o grau de saída)
  29. 29- A soma dos graus de entrada e a soma dos graus de saída de todos os vertices em um grafo com arestas orientadas sãoas mesmas e iguais a o número de arestas no grafo, já que cada aresta tem um vértice final e um vértice final.
    Seja G = (V, E) um grafo com arestas orientadas. Entao
    Σgr⁺(v) = Σgr⁻(v) = |E|
  30. 30- O grafo não orientado que resulta de ignorar as direções das arestas de um grafo com arestas orientadas é chamado deGrafo não orientado subjacente
  31. 31Grafos CompletosO grafo completo de n vertices, indicado por Kn, é o grafo simples que contém exatamente uma aresta entre cada par de vertices distintos.
  32. 32(grafo) CicloO ciclo Cn, n ≥ 3, consiste em n vertices v₁, v₂, v₃, ..., Vn e arestas {v₁, v₂}, {v₂, v₃}, ..., {Vn-₁, Vn} e {Vn, v₁}.
  33. 33(grafos) RodasObtemos a roda Wn quando adicionamos mais um vértice ao ciclo Cn, para n ≥ 3, e conectamos esse novo vértice a cada um dos n vértices em Cn, por novas arestas.
  34. 34(grafos) n-CubosIndicado por Qn, é o grafo que tem vértices que representam as 2ⁿ sequências de bit de comprimento n.
  35. 35- TEOREMA: Se G é um grafo simples, então G ou G‾ (complemento) é conexo - é possível caminhar entre quaisquer dois vértices sobre as arestas."ou" matemático!! Os dois podem ser conexos ou pelo menos um deles é conexo.
  36. 36- TEOREMA: Seja G um grafo conexo com n = |V(G)| e m = |E(G)|. Então G é uma árvore <-> (sse) m = n - 1.- se m = n - 1, G é árvore
    - Se G é árvore, m = n - 1
  37. 37- H é um subgrafo de G seV(H) ⊂ V(G) e E(H) ⊂ E(G).
  38. 38- Um subgrafo é gerador seV(H) = V(G), ou seja, se possui apenas arestas a menos.
  39. 39- Um subgrafo é induzido sepossui todas as arestas de G dentro de V(H), ou seja, se remover vértices de G e suas arestas, mas nunca só uma aresta.
  40. 40- TODO grafo possui pelo menos uma árvore geradora!!!!
  41. 41- Um grafo G é dito bipartido seo seu conjunto V de vértices pode ser dividido em dois conjuntos distintos V₁ e v₂ tal que cada aresta do grafo conecta um vértice em V₁ e um vértice em v₂ (de modo que nenhuma aresta em G conecta dois vértices, seja em V₁, seja em v₂). Chamamos o par (V₁, v₂) de BIPARTIÇÃO do conjunto de vértices V de G.
  42. 42- TEOREMA: Um grafo simples é bipartido se e somente se for possível associar uma de duas cores diferentes a cada vértice do grafo de modo que nenhum par de vértices adjacentes tenham a mesma cor associada..
  43. 43O grafo bipartido completo Km,n é um grafo quetem seu conjunto de vertices dividido em dois subconjuntos de m e n vertices (classes de tamanho m e n), respectivamente. Existe uma aresta entre dois vertices se e somente se um vértice estiver no primeiro subconjunto e o outro vértice no segundo subconjunto.
    É bipartido completo se todos os vértices de m estiverem ligados a todos os vértices de n, mas não entre si.
  44. 44- TODA ÁRVORE é um grafo BIPARTIDO(testa-se colorindo e percebe-se que só são utilizadas 2 cores)
  45. 45- TEOREMA: G é um grafo bipartido SSE não contém ciclo ímpar como subgrafo.!!
  46. 46- Um emparelhamento (ou pareamento) em um grafo simples éum subconjunto de arestas tal que nenhuma delas compartilha um vértice em comum. Em outras palavras, é um conjunto de arestas disjuntas por vértices.
  47. 47- Grafos que têm valores associados a cada aresta são chamados degrafos com peso.
  48. 48- O comprimento de um caminho em um grafo com peso éa soma dos pesos das arestas desse caminho.
  49. 49Circuito EulerianoSequência de vértices vizinhos (passeio), que não repete arestas (trilha), termina onde começou (circuito) e usa todas as arestas.
  50. 50Euler mostrou que se o grau de todos os vértices em um grafo é par, então existe circuito euleriano..
  51. 51- TEOREMA: Um multigrafo conexo com, pelo menos, dois vértices tem um ciclo euleriano se e somente se cada um de seus vértices tiver grau par.- Se um multigrafo conexo tiver todos os vértices com grau par, tem circuito euleriano
    - se um grafo tem circuito euleriano, entoa todos os vértices têm grau par
  52. 52- TEOREMA: Um multigrafo conexo tem um caminho euleriano, mas não um ciclo euleriano se e somente se tiver exatamente dois vértices de grau ímpar..
  53. 53Ciclo HamiltonianoSequência de vértices vizinhos (passeio), que não repete vértices (caminho), termina onde começou (ciclo) e usa todos os vértices.
  54. 54- TEOREMA: Se G for um grafo simples com n vértices com n ≥ 3 tal que o grau de todo vértice em G seja, pelo menos, n/2, então G tem um ciclo hamiltoniano. - TEOREMA: Se G for um grafo simples com n vértices com n ≥ 3 tal que gr(u) + gr(v) ≥ n para cada par de vértices não adjacentes u e v em G, então G tem um ciclo hamiltoniano.*** os últimos dois teoremas oferecem condições suficientes para que um grafo conexo tenha um ciclo hamiltoniano, mas não necessárias para a existência de um ciclo hamiltoniano.
  55. 55- Um grafo é dito planar seele puder ser desenhado no plano sem quaisquer arestas se cruzando.
  56. 56- TEOREMA: Se G é um grafo planar e conexo, desenhado no plano, então n - m + f = 2 (n: vértices, m: arestas, f: faces). Ou r = e - v + 2 (r: regiões)..
  57. 57- COROLÁRIO: Se G é planar conexo com n vértices e m arestas, em que n ≥ 3, então m ≤ 3n - 6 (o número de arestas é, no máximo, 3x o número de vértices menos 6).OBS: O contrário não é necessariamente válido!
  58. 58- COROLÁRIO: Se G é um grafo simples planar conexo, então G tem um vértice de grau que não excede 5..
  59. 59- Ao colorir um grafo G, cada cor forma umconjunto independente (não tem aresta conectando os vértices dentro de um mesmo conjunto, apenas vértices entre conjuntos).
  60. 60- Número cromático de um grafo éo menor número de cores necerrárias para a coloração deste grafo.
  61. 61- TEOREMA DAS 4 CORES: O número cromático e um grafo planar não é maior do que quatro..
  62. 62- Se G possui um Kn dentro, então o número cromático (quantidade mínima de cores para pintar os vértices de um grafo de modo que dois vizinhos não tenham a mesma cor) épelo menos n.
  63. 63- Uma coloração gulosa éuma coloração em que as cores são ordenadas e os vértices são previamente ordenados e coloridos com a menor cor disponível. O resultado depende da ordem dos vértices.

Information

Description
1º ano Matemática Flashcards on Mat Disc - Grafos, created by Raiza Wunsch on 15/01/2025.
Created by
Raiza Wunsch
Views
0
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?