Scribd
Upload
470 views22 pages

Understanding Graphs in Modeling

The document discusses graph theory and defines graphs as sets of vertices connected by edges. It provides examples of undirected and directed graphs. Graphs can model real-world situations like connections between barangays or social network friends. Different types of graphs are explored, including directed graphs, multigraphs with multiple edges or loops, null graphs with no edges, paths between vertices, and complete graphs where all vertices are connected. The document aims to explain how to model systems and relationships using graphs.

Uploaded by

Fatimah Rahima Jingona
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
470 views22 pages

Understanding Graphs in Modeling

The document discusses graph theory and defines graphs as sets of vertices connected by edges. It provides examples of undirected and directed graphs. Graphs can model real-world situations like connections between barangays or social network friends. Different types of graphs are explored, including directed graphs, multigraphs with multiple edges or loops, null graphs with no edges, paths between vertices, and complete graphs where all vertices are connected. The document aims to explain how to model systems and relationships using graphs.

Uploaded by

Fatimah Rahima Jingona
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 22

Mathematics in the Modern World

Module 3 – Topic 3
Graph Theory
Lesson 1: Modelling with Graphs
Learning Outcomes
At the end of the lesson, students should be able to:

1. State and explain the formal definition (set theoretic) of a


graph;

2. Configure a graph in several ways and determine if a graph is


indeed realizable; and

3. Set-up graph models in real-life situations.


Definitions

A graph is a set of points called vertices and line segments called


edges that connect vertices.
Definitions
A graph, usually denoted as G, has two important components:
i) V - a set of vertices (or nodes)
ii) E - a set of edges (or lines) E.
The set E consists of pairs of the elements of V.

If the pairs are ordered, then the resulting graph is said to


be directed, otherwise it is undirected. In both cases, we specify a
graph G as
G = (V,E).
The cardinality of V is referred to as the order of the graph while the
cardinality of E is its size.
Definitions
If 𝑥 and 𝑦 are vertices of a graph G, that is, 𝑥, 𝑦 ∈ V then an edge 𝑒
can be denoted as 𝑒 = (𝑥, 𝑦) ∈ E. In this case, the vertices 𝑥 and 𝑦 are
said to be adjacent and that the edge 𝑒 is incident on 𝑥 (or on 𝑦).

The degree of a vertex is the number of edges incident to it, or


equivalently, the number of vertices that are adjacent to it.
Example: Simple Undirected Graph
G = ({A,B,C,D,E,F},{{A,B},{A,C},{A,D},{D,E},{D,F}}) = (V,E)

V E
B A C

order: |V| = 6
size: |E| = 5

E D F
Example: Simple Undirected Graph

G = ({A,B,C,D,E,F},{{A,B},{A,C},{A,D},{D,E},{D,F}}) = (V,E)

V E
B A C
For brevity, use AB to mean the edge {A,B}.

G = ({A,B,C,D,E,F},{AB,AC,AD,DE,DF}).

Vertex degrees:
Vertex A B C D E F
Degree 3 1 1 3 1 1
E D F
Remarks

1. The lengths of the edges do not matter.


2. The location of the vertices does not matter.
3. Edges are not limited to straight lines; curved lines (or arcs) may
also be used.
4. The relative placement of the vertices does matter.
5. Graphs may appear different in form but as long as the adjacency
is followed based on the edge set E, then such graphs refer to the
same graph (isomorphism of graphs).
Isomorphic Graphs

G = ({A, B, C, D, E}, {AB, AC, AE, BC, BD, CE})


Graph Model
Consider five barangays B1, B2, B3, B4, and B5 all located in Manila.
A certain agency involved in community development is implementing
a new project in these five barangays and is interested to know how
the residents can access the nearby barangays. The clustered map of
these barangays is shown below. Set up a model for the five
barangays.
Graph Model
Graph Model
Graph Models

Teacher Ed is examining how his six students, Kim, Ken, Joel, Tom,
Jon and Migs, are connected in Facebook(FB). His initial data
revealed the following information (a check mark means being FB
friends)
Discussion Proper
Discussion Proper
Types of Graphs

Directed Graphs

H = ({A,B,C,D,E,F},{(A,C),(A,B),(B,A),(D,A),(B,E),(B,F)})
Directed Graphs

Because of the direction, there is a need to identify the


initial and terminal vertices, like in the edge (A,B), vertex
A is the initial while vertex B is the terminal vertex. Edges
that are directed towards a vertex comprise the in degree
of the vertex while those that are directed away comprise
the out degree.
Types of Graphs

Multigraph

G = ({A,B,C},{AB,AB,AB,BC,CC})

Multi-edge Loop
Types of Graphs

Null Graph

G = ({A,B,C}, ∅ )
Types of Graphs

Paths
Types of Graphs

Cycles
Types of Graphs

Complete Graphs

You might also like