Fiche de révision : Fundamentals of Graph Theory

📋 Course Outline

1. Graph definition and components
2. Graph vocabulary and types
3. Graph properties and characteristics
4. Degree and order of graphs
5. Types of graphs and applications

📖 1. Graph definition and components

🔑 Key Concepts & Definitions

• Graph: An set composed of two parts: a set of points called vertices and a set of segments called edges connecting some pairs of vertices (G = (S, A)).
• Vertices (or nodes): Points in a graph representing entities. They are the fundamental units of the graph.
• Edges (or links): Segments that connect pairs of vertices, representing relationships or connections between entities.

📝 Essential Points

• A graph is characterized by its vertices and edges.
• The set of vertices is often denoted as S = {S1, S2, S3, ..., Sn}.
• The set of edges is often denoted as A = {A1, A2, A3, ..., An}.
• The number of vertices is called the cardinality of S (denoted as s).
• The number of edges is called the cardinality of A (denoted as n).
• A graph can be represented as G = (s, n), where s is the number of vertices and n is the number of edges.

💡 Key Takeaway

A graph is a structure composed of points called vertices and segments called edges that connect some pairs of these vertices, serving as a fundamental model for representing relationships between entities.

📖 2. Graph vocabulary and types

🔑 Key Concepts & Definitions

• Vertex: A point in a graph representing an entity (also called a node).
• Edge: A segment connecting two vertices, representing a relationship or connection.
• Loop: An edge that connects a vertex to itself.
• Multiple edges: Several edges between the same pair of vertices.
• Chain: A sequence of edges connected consecutively.
• Cycle: A chain whose two ends are the same vertex, forming a closed loop (circuit in directed graphs).
• Graph types:
  • Simple graph: Contains no loops or multiple edges.
  • Complete graph: Every pair of distinct vertices is connected by an edge.
  • Directed graph: Edges have a direction, indicated by arrows.
  • Connected graph: There exists a path between any two vertices.
  • Stable graph: Contains no edges; no vertices are connected.

📝 Essential Points

• A vertex is a fundamental point in a graph.
• An edge links two vertices; it can be a loop (connecting a vertex to itself) or multiple edges (more than one edge between the same vertices).
• A chain is a sequence of connected edges, and a cycle is a chain that starts and ends at the same vertex.
• Graph types are distinguished by properties such as the presence of loops, multiple edges, and connectivity.
• A simple graph excludes loops and multiple edges.
• A complete graph has all vertices mutually adjacent.
• A directed graph assigns a direction to each edge.
• A connected graph allows a path between any two vertices.
• A stable graph has no edges at all.

💡 Key Takeaway

Graph vocabulary includes various fundamental terms describing points, connections, and structures, which are essential for understanding different graph types and their properties.

📖 3. Graph properties and characteristics

🔑 Key Concepts & Definitions

• Order: The total number of vertices (or points) in a graph.
  Example: A graph with 5 vertices has an order of 5.

• Degree of a vertex: The number of edges incident to a vertex.
  Note: In the case of a loop (an edge connecting a vertex to itself), the loop counts twice towards the degree of that vertex.

• Maximum degree: The highest degree among all vertices in the graph.
  Example: If vertices have degrees 2, 3, and 4, the maximum degree is 4.

• Sum of degrees: The total of the degrees of all vertices in the graph.
  Property: In a simple graph, this sum equals twice the number of edges.

• Presence of loops: A loop is an edge that connects a vertex to itself.

• Multiple edges: Several edges connecting the same pair of vertices.

• Adjacency: Two vertices are adjacent if there is exactly one edge connecting them.

• Isolated vertices: Vertices with no incident edges; they are not connected to any other vertices.

📝 Essential Points

• The order indicates how many vertices are in the graph.
• The degree of a vertex counts all incident edges; loops count twice.
• The maximum degree is the highest degree among all vertices, reflecting the most connected vertex.
• The sum of degrees of all vertices in a simple graph equals twice the total number of edges.
• A loop connects a vertex to itself; multiple edges are several edges between the same vertices.
• Adjacency is determined by the presence of a connecting edge between two vertices.
• An isolated vertex has a degree of zero, indicating no connections.

💡 Key Takeaway

Graph properties such as order, degrees, and characteristics like loops, multiple edges, adjacency, and isolated vertices provide fundamental insights into the structure and connectivity of a graph.

📖 4. Degree and order of graphs

🔑 Key Concepts & Definitions

• Degree of a vertex: The number of edges incident to that vertex. In the case of a loop (an edge connecting a vertex to itself), the loop counts twice towards the degree of that vertex (GPM 3 (date): "the loop is counted for two times during the degree of this vertex").
• Order of a graph: The total number of vertices in the graph (GPM 3 (date): "the order of a graph is the number of total vertices of this graph").

📝 Essential Points

• The degree of a vertex indicates how many connections it has with other vertices.
• The order of a graph is simply the count of all vertices present.
• In graphs, the sum of the degrees of all vertices equals twice the number of edges, especially in simple graphs (no loops or multiple edges).
• The degree of a graph is the maximum degree among all vertices.
• For a vertex with a loop, the loop contributes twice to its degree.
• The number of edges can be deduced by summing all vertex degrees and dividing by two.

💡 Key Takeaway

The degree of a vertex measures its connectivity, while the order of a graph indicates its size; together, these concepts help analyze the structure and properties of graphs.

📖 5. Types of graphs and applications

🔑 Key Concepts & Definitions

• Applications of graphs: Using graphs to model real-life situations such as transportation, social interactions, communication networks, and scheduling problems. These models help visualize and analyze complex systems by representing entities and their relationships.

• Graph types and their applications:

  • Complete graphs: Graphs where every pair of distinct vertices is connected by an edge. Used for fully connected networks where all entities interact directly.
  • Directed graphs: Graphs where edges have a direction, indicating one-way relationships. Suitable for modeling systems like traffic flow or communication channels with unidirectional links.
  • Connected graphs: Graphs in which there is a path between any two vertices. They represent networks where all entities are reachable from each other, essential for ensuring connectivity in communication or transportation systems.

📝 Essential Points

• Applications of graphs include modeling various real-life systems such as transportation routes, social interactions, communication networks, and scheduling.
• Complete graphs are used when all entities are interconnected, exemplifying fully connected networks.
• Directed graphs are applicable when relationships are one-way, such as traffic directions or data flow.
• Connected graphs are important for ensuring that all parts of a network are reachable, which is crucial in network connectivity scenarios.

💡 Key Takeaway

Graphs serve as versatile tools for representing and analyzing real-world systems, with specific types like complete, directed, and connected graphs tailored to different application needs.

📊 Synthesis Tables

⚠️ Common Pitfalls & Confusions

1. Confusing vertices with edges; vertices are points, edges are connections.
2. Miscounting loops as only one incident edge; loops count twice for the degree.
3. Assuming all graphs are simple; many graphs may contain multiple edges or loops.
4. Mixing up connected (path between any two vertices) with complete (every pair connected).
5. Forgetting that the sum of all vertex degrees in a simple graph equals twice the number of edges.
6. Overlooking that in directed graphs, edges have a direction, affecting adjacency and path calculations.
7. Misidentifying stable graphs as having edges; stable graphs have no edges at all.

✅ Exam Checklist

• Know the definition of a graph as a set of vertices (S) and edges (A) and the notation G = (S, A).
• Understand the difference between vertices and edges, including terminology like loops, multiple edges, chains, and cycles.
• Be able to distinguish between simple, complete, directed, connected, and stable graphs, including their properties.
• Master the concepts of graph order (number of vertices) and degree (number of incident edges), including how loops count twice.
• Recall that the sum of all vertex degrees in a simple graph equals twice the number of edges.
• Know SMITH's definition of the invisible hand (if relevant to the course content).
• Understand the applications of different graph types in real-world modeling.
• Be familiar with the properties and characteristics of graph connectivity and how they influence network analysis.
• Recognize the importance of adjacency, isolated vertices, and their implications for graph structure.
• Be able to analyze and classify graphs based on their properties and types.
• Know the key authors and their concepts related to graph theory, especially GPM 3 regarding loops and degrees.
• Review all vocabulary terms and definitions related to graph components and types.