Chapter 7 : Graphs and Trees Flashcards
1
Q
What is the application of Graphs?
A
- Social Networks
- Communications Networks
- Information Networks
- Transportation Networks
2
Q
What are the Graphs mean in this chapter?
A
- A particular class of discreate structures that is useful for representing relations and has a convenient webby-looking graphical representation
3
Q
List out the 2 types of graphs
A
- Undirected Graphs
- Directed Graphs
4
Q
Fill in the blank and describe G = ( _ , _ )
A
- V
- E
- Description
V, a nonempty set of vertices ( nodes )
E , a set of edges
G = ( V , E )
V = { V1, V2 }
E = { { V1, V2} , {V2, V1} }
5
Q
What does Undirected Graph have?
A
- Simple Graph
- Multigraph
- Pseudograph
6
Q
What is the definition of Simple Graph?
A
- Each edge connects 2 different vertices and where no 2 edges connect the same pair of vertices is called a simple graph
A → B → C
- Simple graph has not loop and no multiple edges
7
Q
What edges that Multigraph have than Simple graphs?
A
- Multiple edges connecting the same vertices
A → B
A ← B
8
Q
What edges that Pseudograph have to be called as Pseudographs? ( 2 )
A
- Include loops
- Multiple Edges ( Optional ) → Like multigraph
⋂
A
9
Q
When the graph is Simple Directed Graph?
A
- When a directed graph has no loops and no multiple directed edges ( multiedges )
- Multiedges
A → B
A → B
2 Line going to the same direction
10
Q
When the graph is Directed Multigraph?
A
- Graphs that may have multiples directed edges from a vertex to a second vertex to model networks
- Graphs that have multieges
11
Q
What does Vertices represented in?
A
- dot .
- It is also called as Nodes
12
Q
What does Edges represented in?
A
- line
______
Use both Vertices and Edges to create a graph
13
Q
What is Adjacent?
A
- A vertex connected to another vertex1 — 2
|
3
Node 1 and 2 are adjacent because they are connected
Node 2 and 3 are not adjacent because they are not connected by edge
It’s about a direct connection
Adjacent nodes are “next to” each other
14
Q
What is Incident?
A
- A vertex connected to an edge1 — 2 (edge ‘e1’)
| (edge ‘e2’)
3
Edge e1 is incident to 1 and 2
Edge e2 is incident to 1 and 3
Node 1 is incident to e1 and e2
Node 3 is incident to e2
*It’s about an edge “touching” or being connected to a node at its end**
An incident edge “ends at” a node
15
Q
What is a degree?
A
- Number of Edges incident with the Vertices
- Denoted by deg(v) where v is a vertex
16
Q
Calculate degree below:
1. A → B
→ C
→ D
2. ⋂ ( Loop )
A
A
- deg(A) = 3
- deg(A) = 2
17
Q
What is degree 0 called?
A
- Isolation
18
Q
What is in-degree? And list out the terminology
A
- Arrows going in
- deg ⁻(V)
19
Q
What is out-degree? And list out the terminology
A
- Arrows going out
- deg ⁺(V)
20
Q
Why does the loop at a vertex contributes 2 in degree?
A
- Because a loop has both in-degree and out-degree
Undirected
- Degree
Directed
- In-Degree
- Out-Degree
21
Q
What does Handshaking Theorem calculates in Undirected Graph?
A
- Calculate the total number of degree in a Undirected Graph
- In Directed Graph, the method calculate different things
22
Q
How many edges are there in a graph with 10 vertices each of degree six
A
10 x 6 = 2e
60 = 2e
e = 30
Total Degree = 10 x 6 since each vertices has 6 degree ( 6 + 6 + 6 + … + 6 = 60 )
23
Q
How many edges are there in a graph with 5 vertices each of degree 3?
A
5 x 3 = 2e
15 = 2e
e = 7.5
∴ Graph doesn’t exist
24
Q
Draw a simple undirected graph whose degree sequence is
1. ( 1 , 1 , 2 , 2 , 4 )
A
2 ———— 2
\ /
\ /
\ /
1——4——-1
1 + 2 + 2 + 1 + 4 = 2e
10 = 2e
e = 5
Draw the most number of edges first ( 4 in this question ), then extend it
25
Draw a simple undirected graph whose degree sequence is
1. ( 0 , 0 , 1 , 1 )
0 1
|
0 1
Actually should be dot for the 0 and 1's
1 + 1 = 2e
e = 1
26
Draw a simple undirected graph whose degree sequence is
1. ( 1 , 2 , 3 , 4 , 5 )
1 + 2 + 3 + 4 + 5 = 2e
15 = 2e
e = 7.5
∴ Graph doesn't exist
27
List out 2 ways to represent graph in a formal way
1. Adjacency List ( Table )
2. Adjacency Matrices ( Matrix )
28
Use adjacency list to describe the simple graph given below
⋂
b
/
a ------------------- c
\ / |
\ / |
e ----------- d
Vertex Adjacent Vertices
a b, c , e
b a , b ( Loop )
c a , d , e
d c , e
e a , c , d
29
Use adjancency matrix to describe the simple graph below
⋂ ( At b )
a ------------- b
c d
c to b , a to d
| \ / |
| \ / |
| / \ |
| / \ |
a b c d
a 0 1 1 1
b 1 1 1 1
A₁ = c 1 1 0 0
d 1 1 0 0
* Loop is counted as 1 ( b , b )
* Should hava [ ] covering the number and the a b c d is outside the []
30
What is a path?
1. Is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph
A -> B -> C -> D is a simple path of length 3.
31
What is the condition of circuit?
1. If the path begins and ends at the same vertex
32
What is the condition of Euler Circuit?
1. Cover all vertices ( At least once )
2. Cover all edges ( Exactly once )
3. All even degree
4. Start and End at the same vertices
deg ( a ) = 2
deg ( b ) = 2 -> All even degree
* Starts with a and ends with a
33
What is the condition of Euler Path?
1. Cover all vertices ( At least once )
2. Cover all edges ( Exactly once )
3. Exactly 2 odd degree
deg ( a ) = 1
deg ( b ) = 1 -> Exactly 2 odd degree
* Starts with a and ends with b
34
What is the condition of Hamilton Path?
1. Cover all vertices ( Exactly once )
2. Cover some edges ( Exactly once )
a - b
|\/ |
d - c
a, b ,c ,d ( Don't need to cover all edges )
35
What is the condition of Hamilton Circuit?
1. Cover all vertices ( Exactly once )
2. Cover some edges ( Exactly once )
3. Start and End at the same vertex
a - b
|\/ |
d - c
a, b ,c ,d, a ( Don't need to cover all edges )
Reasons for no Hamilton Path : The degrere of f ( other vertices ) is 1
36
How to know if the graph has a subgraph?
1. Connect all Vertices
2. Number of Vertices = Number of Edges
3. All Vertices degree is 2
37
What makes Hamilton Circuit doesn't exist?
1. Articulation Vertex
a ------- d
| \ / |
| c |
| / \ |
b ------- e
* C is an Articulation Vertex
38
What are the graphs called when the graphs have a number assigned to each edge?
1. Weighted Graphs
* Questions will ask the shortest path
39
Wht is the length of a shortest path between a and z in the weighted graph shown in Figure?
```
3
b ---------- c
4 / \ \ 2
a \ z
2 \ \ / 1
d ------------ e
3
```
The shortest path is a - d - e - z and the length of the shortest pth from a to z is 6 ( 2 + 3 + 1 )
40
What is a planar graph?
1. A vertices link to another vertices wihout crossing edges
```
|-------------
a --- b |
c --- d ----- | a to d
```
| | |
41
What is the condition of nonplanar graph?
1. A graph cennot be drawn in a plan ( cannot be drawn so that no edge cross )
42
What is graph coloring?
1. An assignment of labels, called colors, to the vertices of a graph such that no 2 adjacent vertices share the same color
```
R G R
a -- b --- d
-- c
B
```
43
What is a chromatic number?
1. Minimal number of colors for which such an assignment is possible
44
What is the chromatic number of planar graph?
1. No greater than 4
**Non-planar graphs have large chromatic numbers**
45
Is the graph below Planner or Non Planner?
```
a ---- b
| \ / |
| e |
| / \ |
c ---- d
```
| \ / |
1. It is a planner graph
* Non planner graph is where 2 edges are together
```
a ---- b
| / \ |
c ---- d
```
| \ / |
46
What are the tips for determining the chromatic number of graph?
1. Start from Left to Right
2. Try staying R , B , B until no colors
47
What are the chromatic numbers of the graph G shown in below figure?
b --- d
/
a
\
c --- e
G R
b --- d
/
R a
\
c --- e
B R
Chromatic Numbers = 3 ( Red, Green, Blue )
48
What is the condition of tree diagram?
1. A connected graph that contains no simple circuits is called a tree
```
a -- c -- d
| /
b
```
Simple Circuit
a, b , c , a
| /
49
List out all 9 tree terminology
1. Parent
2. Child
3. Siblings
4. Ancestors
5. Decendants
6. Root
7. Internal Vertices
8. Leaves
9. Subtree
50
Which is root?
a
/ | \
b c d
1. a
51
Which is parent of b, c , d ?
a
/ | \
b c d
1. a
52
Which is children of a ?
a
/ | \
b c d
1. b , c , d
53
Which is siblings of b ?
a
/ | \
b c d
1. c and d
54
Which is ancestor of e ?
‘’’
a
/ | \
b c d
|
e
‘’’
1. b and a
55
Which is leaves ?
a
/ | \
b c d
|
e
1. e , c and d
* Vertex that has no children
56
Which is decendants of a ?
a
/ | \
b c d
|
e
1. b , c , d and e
57
Which is internal vertices ?
a
/ | \
b c d
|
e
1. a and b
**Vertices with children**
58
List out the subtree for b
a
/ | \
b c d
|
e
| |
i j
1.
b
|
e
| |
i j
59
What is Tree Traversal?
1. Is a procedure for systematically visiting each vertex of an order rooted tree to access data
60
List out 3 tree traversal algorithm
1. Preorder
2. Inorder
3. Postorder
61
List out 2 steps for doing Preorder
1. Visit Root
2. Subtrees Left to Right
* Easier method ( Following The Wall )
1. Draw Nodes Left to Right for trees first
2. Move to left side from root
3. Reach to one node and write
4. Continue Step 3
* More on Notion Notes
62
List out 3 steps for doing Inorder
1. Leftmost Subtree
2. Visit Root
3. Visit other Subtree Left to Right
* Easier method ( Following The Wall )
1. Draw Nodes Left to Right for trees first
2. Move to left side from root
3. Reach to one node
4. Proceed to another nodes
5. After reaching the nodes for the **second time**, write the node
* More on Notion Notes
63
List out 2 steps for doing postorder
1. Visit Subtrees Left to Right
2. Visit Root
* Easier method ( Following The Wall )
1. Draw Nodes Left to Right for trees first
2. Move to left side from root
3. Reach to one node
4. Proceed to another nodes
5. After reaching the nodes for the **last time**, write the node
* More on Notion Notes
64
List out 3 Tree Traversal Algorithm
1. Preorder
2. Inorder
3. Postorder
65
List out 2 steps for writing out Preorder
1. Visit Root
2. Subtrees Left to Right
66
List out 3 steps for writing out Inorder
1. Leftmost Subtree
2. Visit Root
4. Visit other Subtree Left to Right
67
List out 2 steps for writing out Postorder
1. Visit Subtrees Left to Right
2. Visit Root
68
Do preorder traversal for the graph below
```
a
↙ ↓ ↘
b c d
↙ ↘ ↙ ↓ ↘
e f g h i
↙ ↘ ↙↘
j k l m
↙↓ ↘
n o p
```
Iteration 1
```
a b c d
↙ ↘ ↙ ↓ ↘
e f g h i
↙ ↘ ↙↘
j k l m
↙↓ ↘
n o p
```
Iteration 2
```
a b e f c d g h i
↙ ↘ ↙↘
j k l m
↙↓ ↘
n o p
```
Iteration 3
```
a b e j k f c d g l m h i
↙↓ ↘
n o p
```
Iteration 4
a b e j k n o p f c d g l m h i
69
Do inorder traversal for the graph below
```
a
↙ ↓ ↘
b c d
↙ ↘ ↙ ↓ ↘
e f g h i
↙ ↘ ↙↘
j k l m
↙↓ ↘
n o p
```
j e n k o p b f a c l g m d h i
70
Do postorder traversal for the graph below
```
a
↙ ↓ ↘
b c d
↙ ↘ ↙ ↓ ↘
e f g h i
↙ ↘ ↙↘
j k l m
↙↓ ↘
n o p
```
j n o p k e f b c l m g h i d a
71
List out steps to do a spanning tree
1. Get all Vertices ( n )
2. Calculate ( n - 1 ) Edges
3. Connect n of Vertices with ( n - 1 ) Edges
* Spanning Tree cannot be Simple Graph
72
Five roads must be plowed to ensure that there is path between any 2 towns. How can this be done?
```
Etna ------ Old Town
/ | \ / \
/ | \ / \
Herman | Bangor ----- Orono
\ | /
Hampden
```
6 Vertices
5 Edges to form Spanning Tree
Etna ----------- Old Town
/ | / \
/ | / \
Herman | Bangor Orono
|
Hampden
