Graph Theory

Graph Theory 

It is the study of graphs, which are mathematical structures used to model pairwise relations of objects.

Russia

Where did Graph Theory originated from?

Leonhard Euler

Who invented Graph Theory?

undirected graph, adjacent

An __________ G consists of a set V(G) of vertices and a set E(G) of edges that which join two vertices. Vertices u and v are ________ if they are joined by an edge. This edge is denoted by uv.

order

The _______ of G, denoted by |V(G)|, is the number of vertices in G.

size

The ________ of G, denoted by |E(G)|, is the number of edges in G.

multiple edge

If there is more than one edge joining vertices u and v, then G contains a ___________.

loop

An edge from a vertex u to itself is called a _________.

multigraph

If a graph G contains multiple edges or loops, then G is called a _________. Otherwise, G is called a simple graph.

simple graph

If a graph G contains multiple edges or loops, then G is called a multigraph. Otherwise, G is called a _____________.

Simple Graph

What type of graph is this?

Multigraph

What type of graph is this?

degree, deg_G(u)

The _______ of the vertex u, denoted by ________ is the number of edges that are incident to the vertex u.

neighborhood, N_G(u)

The ________ of u, denoted by _________, is the set of all vertices that are adjacent to u.

walk

A _______ of length k from vertex v₀ to vertex v_k is a sequence (v₀, v₁, …, v_k-1, v_k) of vertices such that two consecutive vertices are joined by an edge. This is denoted by: (v₀, v₁, …, v_k-1, v_k)

Path

The walk (v₀, v₁, …, v_k-1, v_k) is called a ______if v₀, v₁, …, v_k-1, v_k are distinct.

cycle

The walk (v₀, v₁, …, v_k-1, v_k) is called a ______if v₀, v₁, …, v_k-1, v_k are distinct and  v₀ = v_k 

True

True or False: All paths are walk?

False

True or False: All walks are path?

Connected Graph

A graph that always has a path from a vertex to another.

Disconnected Graph

A graph that doesn’t always have a path from a vertex to another.

weighted graph

We say that graph G is a ________ if all the edges of G are assigned with numerical values.

directed, arc, initial vertex, terminal vertex, order, size

A ________ graph D consists of a set V(D) of vertices and a set A(D) of arcs that are formed using (ordered) pairs of vertices in V(D).
An _______from u to v is written as [u,v]. In this case, we say u is the __________ while the vertex v is the _________.

Similar to undirected graphs, the _______ is the number of vertices of the digraph and the ______ is the number of arcs.

Djikstra’s Algorithm

It is a tool for determining a shortest path from a starting vertex s to any destination vertex. It applies to connected simple graphs (directed or undirected).

Permanent, Temporary

What are the two possible status labels in Djikstra’s Algorith?

shortest distance

Once a vertex reaches permanent status label, that means we have determined its ___________ from the starting point.

the same

Two cycles is considered (the same/not the same) if:
(1) they have the same set of vertices
(2) they have different starting point.

No

Is the arc [C,F] same as arc [F,C] in a directed graph? Yes/No

Number of edges it passed through

The length of a walk is equal to?

Number of vertices

What does 6 denote in a path (P₆) or a 5 in a cycle (C₅)?

Yes

Is the number of vertices and number of edge in a cycle the same at all times?

Vertices C and H are adjacent

Which of the following is true?

The graph is a multigraph

The graph has an order of 12

Vertices C and H are adjacent

6

What is the degree of vertex E?

The following are neighbors of vertex E except ______.

vertex A

6

What is the walk length of (A, B, A, B, A, B, A)?

13

What is the size of the given graph?

All of the following edges have a weight of 3 except _______.

Edge CE
Edge EF
Edge BC

Edge BC

8

What is the order of the given graph?

6

What is the shortest distance from Vertex A to Vertex G?

5

How many cycles of length 3 can be found from the given table?

Vertex B

Which is the third current vertex?

4

What is the shortest distance from Vertex A to Vertex E?

4

What is the shortest distance from Vertex A to Vertex C?

5

What is the shortest distance from Vertex A to Vertex H?

6

What is the shortest distance from Vertex A to Vertex G?