# CS代写 MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 – cscodehelp代写

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

Lecture 36 – Matrix Representations of Graphs, Trees.

𝑣𝑣𝑣𝑣 𝑒5 𝑒𝑒𝑒𝑒𝑒 1234 12345

𝑣1 0 1 0 1 𝑣1 0 0 1 1 0

𝐴=𝑣2 1020 𝑁=𝑣2 11100

𝑣3 0 2 0 0 𝑣3 1 1 0 0 0

𝑣1001 𝑣00012 44

Exam revision sessions: Mon 1 Nov 12-1:30pm

Fri 5 Nov 1-2:30pm

Room 7-222 and on Zoom

The mathematics first year learning centre will operate 2-4pm each weekday afternoon until 12 Nov: Room 67-443

and via Zoom.

Learning Goals

Learn how to represent a graph by an adjacency matrix. Learn how to represent a graph by an incidence matrix. Learn how to draw a graph from its adjacency matrix. Learn how to draw a graph from its incidence matrix. Understand the properties of trees.

Student questions and comments:

Incidence matrix – How do you remember which of vertices/edges is the rows and which the columns? Is it ok to swap them?

There are 11 (essentially) different trees with 7 vertices.

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

Lecture 36 – Matrix Representations of Graphs, Trees.

Adjacency matrices for graphs:

The adjacency matrix for a graph with vertices

𝑣1 0 1 0 1 matrix𝐴=𝑣21021

𝑣 , 𝑣 , … , 𝑣 is the 𝑛 × 𝑛 matrix 𝐴 = [𝑎 ] where each 12 𝑛 𝑖𝑗

is the number of edges with endpoints

Activity 1: Write down the adjacency matrix for the graph on the right.

𝑣𝑣𝑣𝑣𝑣 12345

𝑣3 00010 𝑣

Activity 2: Draw the graph for the adjacency matrix on the left.

430101 𝑣5 12010

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

Lecture 36 – Matrix Representations of Graphs, Trees.

Question 1:

Which of the following is an adjacency matrix for a graph?

1022 D. 0 2 0 0 1101

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

Incidence matrices for graphs:

Lecture 36 – Matrix Representations of Graphs, Trees.

The incidence matrix for a graph with vertices

𝑣 , 𝑣 , … , 𝑣 and edges 𝑒 , 𝑒 , … , 𝑒 is the 𝑛 × 𝑚

1 2 𝑛 1 2 𝑚

matrix 𝑁 = [𝑛𝑖𝑗] where each entry 𝑛𝑖𝑗 is the number

Incidence matrix

𝑣1 0 0 1 1 0

of times vertex 𝑣 is incident with edge 𝑒 .

2 1 1 0 0 0 𝑣3

Activity 3: Write down the incidence matrix

for the graph on the right.

𝑣1 2 1 0 0

𝑣2 0 1 0 0

𝑣5 𝑒3 𝑣2 𝑒4

Activity 4: Draw the graph for the incidence matrix on the left.

𝑣1 𝑒4 𝑣 𝑖𝑗4𝑣00012

𝑣 1 1 1 0 0

𝑣3 0 0 2 0 𝑣

4 0001 𝑣5 0 0 0 1

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

Lecture 36 – Matrix Representations of Graphs, Trees.

Question 2:

Which of the following is an incidence matrix for a graph?

0101 1022 0200 1101

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021

A trivial circuit is a circuit consisting of a single vertex and no edges. A non-trivial circuit is a circuit that has edges.

A graph is circuit-free if there are no non-trivial circuits.

Lecture 36 – Matrix Representations of Graphs, Trees.

Definition: A graph is a tree if and only if it is connected and circuit-free.

If any edge is deleted from a tree then the result is a disconnected graph.

This disconnected graph consists of two trees.

Theorem: A graph 𝐺 with 𝑛 vertices is a tree if and only if it is simple, connected and has 𝑛 − 1 edges.

The proof is by induction and the main argument is:-

So the number of edges in the original tree that had 𝑛 + 1 vertices is

𝑝−1 + 𝑞−1 +1=𝑝+𝑞−1.

Since 𝑝 + 𝑞 = 𝑛 + 1, the original tree has 𝑛 edges.

Deleting an edge from a tree with 𝑛 + 1 vertices gives two smaller trees.

Let 𝑝 and 𝑞 be the numbers of vertices in these two smaller trees. By the induction hypothesis they have 𝑝 − 1 and 𝑞 − 1 edges.

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.

Handshake Theorem: The sum of the degrees of a graph is twice the number of edges.

Activity 5:

Every vertex of a tree with 15 edges has either degree 3 or degree 1. How many vertices of the tree have degree 3?

Theorem: A graph 𝐺 with 𝑛 vertices is a tree if and only if it is simple, connected and has 𝑛 − 1 edges.

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.

Activity 6:

A tree has two vertices of degree 4, one vertex of degree 2, and all the other vertices have degree 1. How many vertices does the tree have?

MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.

Activity 7:

Prove that every tree with at least two vertices has at least two vertices of degree 1.