Graph teory

Question 1

Graphs Definition (1)

Answer 1

1.) A graph is defined by a finite set of Vertices and a set of Edges which pare the vertices

Question 2

Edges (1)

Answer 2

1.) Connections between two vertices, which can also be weighted (to assign for example distance)

Question 3

Adjacency Matrixes (3)

Answer 3

1. ) Adjacency matrices of graphs with n vertices is an (n x n) matrix.
2. ) If the graph is unweighted the matrix is boolean and each combination of the elements is equal to 1 if there is an edge and 0 if there isn’t.
3. ) If the graph is weighted the matrix is a weighted/cost matrix and each combination of the elements is equal to the edge weight if there is an edge and infinity if there isn’t.

Question 4

Simple/Strict graphs (4)

Answer 4

1. ) undirected
2. ) unweighted
3. ) no loops
4. ) no more than one edge between two vertices

Question 5

Connected Graphs (1)

Answer 5

1.) Connected graphs: a graph is connected if for any two given points x and y there is a way to travel from x to y.

Question 6

Component (2)

Answer 6

1. ) Disconnected graph which is part of a super graph.

2. ) Also called sub-graph.

Question 7

Complete Graph (3)

Answer 7

1. ) All vertices are connected through direct edges.
2. ) Each vertex will have n-1 edges.
3. ) The graph will have ( n(n-1) ) / 2 edges

Question 8

Cycle Graphs (4)

Answer 8

1. ) Simple, connected graph.
2. ) Each vertex is connected to 2 other vertices.
3. ) The number of edges equals the number of vertices.
4. ) It has a path which starts and ends in the same vertex without traversing an edge more than once.

Question 9

Trees and Forests (3)

Answer 9

1. ) Tree: simple, undirected, connected acyclic graph.
2. ) A tree with n vertices has n-1 edges.
3. ) Forest: supergraph composed by sub-graphs which are trees.

Question 10

Eulerian path/trail (1)

Answer 10

1.) Eulerian path/trail is a path which visits each edge only once.

Question 11

Path (1)

Answer 11

1.) Finite or infinite sequence of edges which connect disconnected vertices.

Question 12

Undirected Graph (2)

Answer 12

1. ) Each edge in the graph is undirected.

2. ) Undirected graphs are symmetric.

Question 13

Directed Graph (2)

Answer 13

1. ) Each edge in the graph is directed.

2. ) Diagraphs are asymmetric.

Question 14

Mixed Graphs (1)

Answer 14

1.) Mixed graphs have both directed and undirected edges.

Question 15

Directed Edges (2)

Answer 15

e = (u, v)

1. ) The edge is directed if (u, v) is not the same as (v, u).
2. ) ‘u’ is called the edge’s tail and ‘v’ is called the edge’s head.

Question 16

Eulerian cycle/circuit (2)

Answer 16

1. ) Eulerian trail which starts and ends on the same vertex.
2. ) If all vertices have an even number of edges then a eulerian cycle is possible

Question 17

Eulerian graph (1)

Answer 17

1.) A graph with an eulerian cycle is a Eulerian graph.

Question 18

Hamiltonian/Traceable path (1)

Answer 18

1.) path in undirected or directed graph which passes by each vertex only once.

Question 19

Hamiltonian cycle/circuit (1)

Answer 19

1.) A hamiltonian path which starts and ends in the same vertex.

Question 20

Hamiltonian Graph (1)

Answer 20

1.) Graphs which have hamiltonian cycles/circuits.

Question 21

Multigraphs (1)

Answer 21

1.) Graphs with multiple edges connecting two vertices.