Graphs (Part A)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 16, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 1 / 14
1 Graph Models
2 Terminologies
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 2 / 14
Introduction
Definition of a Graph
A graph G = (V , E ) consists of V , a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.
• If V is an infinite set or the graph has an infinite number of edges, then it is called an infinite graph.
• If V and E are finite sets, then it is called a finite graph.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 3 / 14
Introductory Definitions
Simple Graph: A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices. In a simple graph, each edge is associated to an unordered pair of vertices, and no other edge is associted to this same edge.
Multigraphs: Graphs that may have multiple edges connecting the same vertices.
Loops: Edges that connect a vertex to itself.
Pseudographs: Graphs that may include loops, and possibly multiple
edges connecting the same pair of vertices or a vertex to itself.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 4 / 14
Introductory Definitions (cont.)
Definition of a Directed Graph
A directed graph (or digraph) (V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.
• When a directed graph has no loops and has no multiple directed edges, it is called a simple directed graph.
• Directed graphs that may have multiple directed edges from a vertex to a second vertex are called directed multigraphs. If there are m edges exist between an ordered pair (u,v), then the edge multiplicity is m.
• A graph with both directed and undirected edges is called a mixed graph.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 5 / 14
Introductory Definitions (cont.)
• As graph theory has applications to a wide variety of disciplines, definitions can vary in the literature.
• Three key questions can help us understand the structure of a graph. (i) Are the edges of the graph undirected or directed (or both)?
(ii) Are multiple directed/undirected edges present?
(iii) Are loops present?
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 6 / 14
Graph Models
Social Networks
Communication Networks Information Networks
Transportation Networks Biologial Networks
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 7 / 14
Basic Terminology
Neighbours
Two vertices u and v in an undirected graph G are called adjacent (or neighbours) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.
Neighbourhood
The set of all neighbours of a vertex v of G = (V,E), denoted by N(v), is called the neighbourhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So, N(A) = v∈A N(v).
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v).
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 8 / 14
Basic Terminology (cont.)
A vertex of degree zero is called isolated.
A vertex is pendant if and only if it has degree one.
The Handshaking Theorem
Let G = (V , E ) be an undirected graph with m edges. Then
2m = v∈V deg(v).
(Note that this applies even if multiple edges and loops are present.)
An undirected graph has an even number of vertices of odd degree.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 9 / 14
Basic Terminology (cont.)
When (u,v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u called the initial vertex, and v is called the terminal or end vertex. The initial vertex and the terminal vertex of a loop are the same.
In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the number of edges with v as their initial vertex.
Note: A loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 10 / 14
Basic Terminology (cont.)
Let G = (V , E ) be a graph with directed edges. Then v∈V deg−(v) = v∈V deg+(v) = |E|.
Node: 1, 2, … Link: 12, 23, …
8 1135611F
Undirected
2 8 5 Directed C
Path: 1-2-3-7, …
Hop:#ofnodestraversed-1 4 7 E
Figure: Examples of weighted network graphs.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 11 / 14
Special Simple Graphs
Complete Graphs
A complete graph on n vertices, denoted by Kn, is a simple graph that contains exactly one edge between each pair of distict vertices.
A cycle Cn, n ≥ 3, consists of n vertices v1, v2, …, vn and edges {v1, v2}, {v2, v3}, …, {vn−1, vn} and {vn, v1}.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 12 / 14
Special Simple Graphs (cont.)
We obtain a wheel Wn, when we add an additional vertex to a cycle Cn, for n ≥ 3, and connect the new vertex to each of the n vertices in Cn, by new edges.
An n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent if and ony if the bit strings that they represent differ in exactly one bit position.
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 13 / 14
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 10a MdH W22 March 16, 2022 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com