Want to create interactive content? It’s easy in Genially!

Get started free

Teorema de Ore

Erica Filipa

Created on October 28, 2022

Start designing with a free template

Discover more than 1500 professional designs like these:

Vaporwave presentation

Animated Sketch Presentation

Memories Presentation

Pechakucha Presentation

Decades Presentation

Color and Shapes Presentation

Historical Presentation

Explore all templates

Transcript

Teorema de Ore

Erica Fernandes, Bárbara Resende, Vitoria Paredes

Quem Criou?

Øystein Ore

Matemático, Noruegues

Seja um grafo conexo e simples com ordem n > 2. Se a soma dos graus de cada par de vértices não adjacentes é maior ou igual a n, então o grafo admite um circuito hamiltoniano

Ordem do grafo= 5Grau dos vértices:V1- 3 V2-3 V3-2 V4-3 V5-3Vértices não adjacentes: V1-V3/ V3-V5/ V4-V2Soma dos graus dos vértices não adjacentes: V1+V3= 3+2=5 V3+V5= 3+2=5 V4+V2= 3+3=6 Circuito Hamiltoniano: V1-V4-V3-V2-V5-V1

Análise do grafo

  • Ao observar o grafo anterior podemos perceber que o mesmo corresponde ás condições do "Teorema de Ore" e admite um circuitohamiltoniano.

Mas todos os grafos Hamiltonianos correspondem ás caracteristicas do "Teorma de Ore" ?

Mas todos os grafos Hamiltonianos correspondem ás caracteristicas do "Teorma de Ore" ?

Ordem do grafo: 10 Grau dos vértices: A-2 F-4 B-2 G-4 C-4 H-4 D-4 I-2 E-2 J-2

Mas todos os grafos Hamiltonianos correspondem ás caracteristicas do "Teorma de Ore" ?

Vértices não adjacentes: AB/ AE/ AF/ AG/ AI/ AH/ AJ/ BD/ BE/ BG/ BJ/ BH/ BI/ CE/ CG/ CH/ CJ/ CI/ DJ/ DH/ DI/ DF/ EJ/ EH/ EF/ EI/ FG/ FJ/ GI/ IJ

Mas todos os grafos Hamiltonianos correspondem ás caracteristicas do "Teorma de Ore" ?

Soma dos graus dos vértices não adjacentes:A+B= 2+2= 4 A+E= 2+2= 4 A+F= 2+4= 6 A+G= 2+4= 6 A+I= 2+2= 4 A+H= 2+4= 6 A+J= 2+2= 4 B+D= 2+4= 6 B+E= 2+2= 4 B+G= 2+4= 6 B+J= 2+2= 4 B+H= 2+4= 6 B+I= 2+2= 4 C+E= 4+2= 6 C+G= 4+4= 8 C+H= 4+4= 8 C+J= 4+2= 6 C+I= 4+2= 6 D+J= 4+2= 6 D+H= 4+4= 8 D+I= 4+2= 6 D+F= 4+4= 8 E+J= 2+2= 4 E+H= 2+4= 6 E+F= 2+4= 6 E+I= 2+2= 4 F+G= 4+4= 8 F+J= 4+2= 6 G+I= 4+2=6 I+J= 2+2= 4 Circuito Hamiltoniano: ADEGJHIFBCA

Mas todos os grafos Hamiltonianos correspondem ás caracteristicas do "Teorma de Ore" ?

Como visto o grafo ao lado corresponde a um Grafo hamiltoniano pois admite um circuito de Hamilton. Apesar das condições do Teorema de Ore não serem respeitadas pois a soma dos vértices dos graus não é maior ou igual a 10 (ordem do grafo), este é hamiltoniano

Obrigada!