Introdução à Teoria dos Grafos – Aula 2 – Alguns problemas simples

Introduction to Graph Theory

Overview of the Lesson

• The lesson introduces a problem related to graph theory, emphasizing that it may not initially appear as a typical graph problem.

• The objective is to utilize graphs as a tool for solving mathematical problems, particularly in competitive exams like OBMEP.

Problem Presentation

• A fictional scenario set in the year 3000 involves traveling between planets: Earth, Mercury, Venus, Pluto, Uranus, Neptune, Saturn, Jupiter, and Mars.

• The central question posed is whether one can travel from Earth to Mars using specified routes among these planets.

Graph Modeling

• The approach involves modeling the problem using graph concepts; each planet represents a vertex and travel routes represent edges.

• Connections between planets are established step by step while drawing the graph.

Analyzing Connections

• Various connections are made: Earth to Mercury, Pluto to Venus, and others until all possible links are explored.

• The instructor highlights limitations in connectivity; certain planets cannot be reached based on existing routes.

Conclusion of Initial Analysis

• It becomes clear that direct travel from Earth to Mars is impossible due to isolated connections within the graph structure.