Week 1 > Warm Up

Question 1

What is a Graph?

Answer 1

1. A set of objects 2. Relations between pairs of objects 3. A Graph G = (V, E)

Question 2

u and v are End Points of e

Answer 2

Question 3

What is the incident of Graph?

Answer 3

u and e are Incident

Question 4

Draw adjacent u and v vertices

Answer 4

Question 5

• Objects: {A,B,C,D}
• Relations: {{A,C},{D,A},{B,D},{C,B}}

Answer 5

Question 6

What is the Directed Graph?

Draw: Objects: {A,B,C,D} A C B D Relations: {(A,C),(D,A),(B,D),(C,B)}

Answer 6

• It is often convenient to consider Directed Edges (Arcs)
• They describe asymmetric relations
• There is a flight from A to B, but not the other way around

Question 7

Are these graphs the same?

Answer 7

Yes, both have 10 vertices and 15 edges

Question 8

What is the degree of a vertex?

Answer 8

Question 9

What is the degree of the graph?

Answer 9

Question 10

Find the degree of a vertex

Answer 10

• The degree of v is 6: deg(v) 6
• The degree of v₆ is 1: deg(v₆) = 1

Question 11

What are the isolated vertices?

1. deg(v_{<span>2</span>}) = ?
2. deg(v₈) = ?
3. deg(v₀) = ?

Answer 11

1. deg(v_{<span>2</span>}) = 2
2. deg(v₈) = 1
3. deg(v₀) = 0

Thus, v₀ is isolated vertice.

Question 12

1. What is the regular graph?
2. Is the graph is a regular graph?

Answer 12

1. See attached
2. Yes, since each vertex has the same degree

Question 13

1. What is the complement graph?

Answer 13

Question 15

Can you complement of graph?

Answer 15

Question 16

What are Graph Paths?

Answer 16

Question 17

What is a simple path of the graph?

Answer 17

A simple path is a walk where all vertices are distinct.

Question 18

A walk of length 6: (e1, e2, e3, e4, e5, e3, , e1)

Question 19

A path of length 4: (e7, e6, e4, e5)

Answer 19

Question 20

Is the path of length 4: (e7, e6, e4, e5) simple?

Answer 20

Question 21

What are cycles in the graph?

Answer 21

Question 22

What is the simple cycle?

Answer 22

Question 23

Draw the cycle

Answer 23

Question 24

Is this a simple cycle? If not, why?

Answer 24

No, since we visited v₅ vertex three times through e_4, e_6, and e_{<span>7</span>}

Question 25

Why is the simple cycle of length 4: (e5, e4, e2, e3)?

Answer 25

Because visited each vertex only once

Question 26

What are the connected graphs?

Answer 26

A graph is called connected if there is a path between every pair of its vertices

Question 27

What is a connected component of a graph?

Answer 27

A connected component of a graph G is a maximal connected subgraph of G

Question 28

Can you mark or color all vertices of the graph making connected components?

Answer 28

Question 29

What are undirected edges? Edge {u, v}

Answer 29

Question 30

Draw Arc (u,v)

Answer 30

The order of vertices matters in braces

Question 31

What is the indegree of a vertex v?

Answer 31

Question 32

What is the outdegree of a vertex?

Answer 32

Question 33

Can you find the indegree and outdegree of v₃?

Answer 33

Question 34

Is (v1, v3, v2) path? If not why?

Answer 34

Question 35

1. What are weighted graphs?
2. Is attached the example of weighted graph?

Answer 35

Yes, since its edges include driving time between a pair of edges

Question 36

What is definition of a weighted graph?

Answer 36

Question 37

Find the path from v₁ to v₆ vertices?

Answer 37