Introdução à Teoria dos Grafos – Aula 3 – Conectando cidades

Introduction to Graph Theory Problem

Overview of the Problem

• The session begins with an introduction to a new problem related to graph theory, emphasizing its simplicity and mathematical nature.

• The problem involves nine creatively named cities (City 1 through City 9) and the construction of roads between them based on specific rules.

Road Connection Rules

• Roads will connect City A to City B if the number formed by their labels (AB) is divisible by 3. For example, City 1 can connect to City 2 because 12 is divisible by 3.

• However, connections are not possible if the resulting number is not a multiple of three; for instance, City 1 cannot connect to City 3 since 13 is not divisible by 3.

Objective of the Problem

• The main question posed is whether it’s possible to travel from City 1 to City 9 using these road connections, given that direct connections may not exist due to divisibility constraints.

Divisibility Criteria Explained

Understanding Divisibility by Three

• A number is divisible by three if the sum of its digits is also a multiple of three. This rule will be applied throughout the problem-solving process.

• Since only two-digit numbers are considered, both digits must be chosen carefully so that their sum meets this divisibility criterion.

Connecting Digits Based on Remainders

• If one digit (A) is a multiple of three, then the other digit (B) must also be a multiple of three for their sum to remain divisible by three.

• Conversely, if A leaves a remainder when divided by three (either remainder one or two), B must leave a different remainder in order for their combined total to be divisible by three.

Graph Construction and Analysis

Identifying Valid Connections

• The analysis continues with identifying which digits can connect based on their remainders when divided by three.

• Specific pairs are established: digits leaving remainder one cannot connect with each other but can connect with those leaving remainder two.

Visual Representation Challenges

• As connections are mapped out visually, it becomes apparent that certain configurations complicate understanding potential routes between cities.

• Adjustments in visual representation are suggested for clarity in analyzing how cities interconnect under these rules.

Understanding Circuit Connections

Class Connections and Limitations

• The speaker discusses the connections between elements in a circuit, emphasizing that only certain elements can be linked based on their classification (green and yellow).

• It is noted that connections can only be made between specific classes of elements, leading to a division in the graphical representation of the circuit.

• A comparison is drawn to previous discussions about planets, illustrating that being in one part of a circuit (red) prevents access to another part (orange), highlighting limitations in connectivity.