Graph theory

Question 1

What does a graph consist of?

Answer 1

A graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

Question 2

What is a simple graph?

Answer 2

A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph.

Question 3

What is an directed graph?

Answer 3

A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u, v) is said to start at u and end at v.

Question 4

What does it mean if two graphs are adjacent?

Answer 4

Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of one edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.

Question 5

What is a degree of a vertex?

Answer 5

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v).

Question 6

What is a vertex of degree zero called?

Answer 6

Isolated.

Question 7

What is The Handshaking Theorem?

Answer 7

Handshaking theorem states that the sum of degrees of the vertices of a graph is twice the number of edges.
Because of this theorem, the following statement is true: An undirected graph has an even number of vertices of odd degree.

Question 8

What are in-degrees and out-degrees?

Answer 8

In a directed graph, the in-degree of a vertex v, denoted by deg−(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the number of edges with v as their initial vertex. Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.

Question 9

Will the sum of the out-degrees be sam as the in-degrees in a directed graph?

Answer 9

Yes, because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and the sum of the out-degrees of all vertices in a graph with directed edges are the same. Both of these sums are the number of edges in the graph.

Question 10

What is a sub-graph?

Answer 10

Sometimes we need only part of a graph to solve a problem. In the graph model for a large network, we can remove the vertices corresponding to the computer centers other than the four of interest, and we can remove all edges incident with a vertex that was removed. When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph

Question 11

What dow it mean if two graph are isomorphic?

Answer 11

when two simple graphs are isomorphic, there is a one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship. Isomorphism of simple graphs is an equivalence relation. In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them

Question 12

What three things must be if two graphs are isomorphic?

Answer 12

They need to have the same amount of vertices, same amount of edges and same amount of degrees. If none of them are the same, the graphs are not isomorphic. A property preserved by isomorphism of graphs is called a graph invariant.

Question 13

In a directed graph, how does a loop contribute regarding the amount of in and out-degrees?

Answer 13

A loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.

Question 14

What is a path?

Answer 14

Informally, a path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these edges. A path of length n from u to v in G is a sequence of n edges e1,…,en of G for which there exists a sequence x0 = u, x1 , …, xn1 , xn = v of vertices such that ei has, for i = 1, …, n, the endpoints xi1 and xi . When the graph is simple, we denote this path by its vertex sequence x0 , x1 , …, xn (because listing these vertices uniquely determines the path).

Question 15

What is a circuit?

Answer 15

The path is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length greater than zero. The path or circuit is said to pass through the vertices x1, x2, …, xn1 or traverse the edges e1, e2, …, en. A path or circuit is simple if it does not contain the same edge more than once.

Question 16

What is a cut vertice?

Answer 16

Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. The removal of a cut vertex from a connected graph produces a subgraph that is not connected. Analogously, an edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge.

Question 17

When is a directed graph considered strongly connected?

Answer 17

A directed graph is strongly connected if there is a path from a to b and from b to a for all pairs of vertices {a, b} in the graph.
For a directed graph to be strongly connected, there must be a sequence of directed edges from any vertex in the graph to any other vertex. A directed graph can fail to be strongly connected but still be in one piece. Remember: any strongly connected directed graph is also weakly connected.

Question 18

How do you measure edge connectivity?

Answer 18

We can also measure the connectivity of a connected graph G = (V, E) in terms of the minimum number of edges that we can remove to disconnect it. If a graph has a cut edge, then we need only remove it to disconnect G. If G does not have a cut edge, we look for the smallest set of edges that can be removed to disconnect it. A set of edges E is called an edge cut of G if the subgraph G − E is disconnected. The edge connectivity of a graph G, denoted by λ(G), is the minimum number of edges in an edge cut of G.

Question 19

When is a directed graph weakly connected?

Answer 19

A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph.
That is, a directed graph is weakly connected if and only if there is always a path between two vertices when the directions of the edges are disregarded. Clearly, any strongly connected directed graph is also weakly connected.

Question 20

What are the necessary and sufficient conditions for the existence of an Euler circuit/path in a connected multigraph?

Answer 20

A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

Question 21

What does Fleury’s algorithm mean?

Answer 21

constructs Euler circuits by first choosing an arbitrary vertex of a connected multigraph, and then forming a circuit by choosing edges successively. Once an edge is chosen, it is removed form the original graph. Edges are chosen successively so that each edge begins where the last edge ends, and so that this edge is not a cut edge unless there is no alternative.

Question 22

What is a Hamilton path?

Answer 22

A simple path in a graph G that passes through every vertex exactly once.

Question 23

What is a Hamilton circuit?

Answer 23

A simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit.

Question 24

What does Dirac’s theorem say?

Answer 24

Dirac’s Theorem says that if G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n2 , then G has a Hamilton circuit.

Question 25

What does Ore’s theorem say?

Answer 25

Ore’s Theorem says that if G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.

Question 26

Does Dirac’s and Ore’s theorem provide necessary conditions to decide if a graph has a Hamiltion circuit?

Answer 26

Both Ores theorem and Diracs theorem provide sufficient conditions for a connected simple graph to have a Hamilton circuit. However, these theorems do not provide necessary conditions for the existence of a Hamilton circuit. The best algorithms known for finding a Hamilton circuit in a graph or determining that no such circuit exists have exponential worst-case time complexity (in the number of vertices of the graph). Finding an algorithm that solves this problem with polynomial worst-case time complexity would be a major accomplishment because it has been shown that this problem is NP- complete. Consequently, the existence of such an algorithm would imply that many other seemingly intractable problems could be solved using algorithms with polynomial worst-case time complexity.