Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 12
1
Graph Theory PART A: BASICS OF GRAPH THEORY: VERTICES, EDGES, DEGREE 2 Basics of Graph Theory: Vertices, Edges, and Degree
❑ Graph theory is a branch of mathematics that deals with the study
of graphs. ❑ Graphs are used to model various real-world scenarios, such as social networks, transportation systems, and more. ❑ In this lesson, we will explore the fundamental concepts of graph theory, including vertices, edges, and degree, and how they are used to analyze and understand graphs. 3 Basics of Graph Theory: Vertices, Edges, and Degree
Learning Objectives: ❑Understand the basic components Discussion: of a graph: vertices and edges. ❑Vertices and Edge ❑Define and calculate the degree of ❑Degree of a Vertex a vertex. ❑Real-World Examples ❑Explore real-world examples to illustrate these concepts. 4 Vertices and Edges
⮚ A graph is a mathematical structure composed of two main elements:
vertices and edges.
⮚ Vertices (singular: vertex) are the points in a graph. They are often represented as dots or circles in graphical depictions.
⮚ Edges are the connections between vertices. They are represented as lines or arcs in graphical depictions. 5 Vertices and Edges
Example:
✔Imagine a simple social network, where people (vertices) are connected to
each other if they are friends. ✔Each person is a vertex, and friendships are represented as edges between them. 6 Degree of a Vertex
⮚ The degree of a vertex is the number of edges connected to it.
⮚ In an undirected graph, the degree is the same as the number of adjacent
vertices.
⮚ In a directed graph, there are two types of degrees: in-degree (incoming
edges) and out-degree (outgoing edges). 7 Degree of a Vertex
Example:
✔Consider a transportation network where cities are represented as vertices,
and roads as edges. ✔The degree of a city represents how well-connected it is in terms of road connections. ✔A city with a high degree is well-connected to other cities, while a city with a low degree might be more isolated. 8 Real-World Examples
Graph theory is widely used in various fields. Let's look at a few practical examples.
Social Networks ✔In social networks like Facebook or Twitter, users are vertices, and connections (friendships or followers) are edges. ✔Analyzing the degree of users can help identify popular individuals or potential influencers. 9 Real-World Examples
Computer Networks ✔In computer networks, devices (computers, routers) are vertices, and connections (cables or wireless links) are edges. The degree of a device can indicate its importance in the network.
Transportation ✔In a transportation system, intersections (or cities) are vertices, and roads (or routes) are edges. The degree of an intersection can reveal traffic congestion or critical junctions. 10 Example Problems
Example #1
Given a graph with 6 vertices and 9 edges, calculate the average degree of its vertices.
Solution: Average Degree = (2 * Number of Edges) / Number of Vertices Average Degree = (2 * 9) / 6 = 3 11 Example Problems
Example #2
In a directed graph, a vertex A has an in-degree of 3 and an out-degree of 2.
What is the total degree of vertex A?
Solution: Total Degree = In-Degree + Out-Degree Total Degree = 3 (in-degree) + 2 (out-degree) = 5 12 Conclusion
⮚ Understanding the basics of graph theory, including vertices, edges,
and degree, is essential for analyzing and solving various real- world problems.
⮚ Graphs are powerful tools for modeling and understanding
relationships and connectivity in a wide range of applications, making them a fundamental concept in mathematics and computer science.
