# Week 1 > Warm Up Flashcards

1
Q

What is a Graph?

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

u and v are End Points of e

A
3
Q

What is the incident of Graph?

A

u and e are Incident

4
Q

Draw adjacent u and v vertices

A
5
Q
• Objects: {A,B,C,D}
• Relations: {{A,C},{D,A},{B,D},{C,B}}
A
6
Q

What is the Directed Graph?

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

A
• 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
7
Q

Are these graphs the same?

A

Yes, both have 10 vertices and 15 edges

8
Q

What is the degree of a vertex?

A
9
Q

What is the degree of the graph?

A
10
Q

Find the degree of a vertex

A
• The degree of v is 6: deg(v) 6
• The degree of v6 is 1: deg(v6) = 1
11
Q

What are the isolated vertices?

1. deg(v<span>2</span>) = ?
2. deg(v8) = ?
3. deg(v0) = ?
A
1. deg(v<span>2</span>) = 2
2. deg(v8) = 1
3. deg(v0) = 0

Thus, v0 is isolated vertice.

12
Q
1. What is the regular graph?
2. Is the graph is a regular graph?
A
1. See attached
2. Yes, since each vertex has the same degree
13
Q
1. What is the complement graph?
A
14
Q
A
15
Q

Can you complement of graph?

A
16
Q

What are Graph Paths?

A
17
Q

What is a simple path of the graph?

A

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

18
Q

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

A
19
Q

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

A
20
Q

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

A
21
Q

What are cycles in the graph?

A
22
Q

What is the simple cycle?

A
23
Q

Draw the cycle

A
24
Q

Is this a simple cycle? If not, why?

A

No, since we visited v5 vertex three times through e4, e6, and e<span>7</span>

25
Q

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

A

Because visited each vertex only once

26
Q

What are the connected graphs?

A

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

27
Q

What is a connected component of a graph?

A

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

28
Q

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

A
29
Q

What are undirected edges? Edge {u, v}

A
30
Q

Draw Arc (u,v)

A

The order of vertices matters in braces

31
Q

What is the indegree of a vertex v?

A
32
Q

What is the outdegree of a vertex?

A
33
Q

Can you find the indegree and outdegree of v3?

A
34
Q

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

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

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

36
Q

What is definition of a weighted graph?

A
37
Q

Find the path from v1 to v6 vertices?

A
38
Q
A
39
Q
A
40
Q
A