Exam

Question 1

Graph

Answer 1

Graph is a triple (V, E and g) where V is a finite nonempty set called the vertices. E is a finite set called the set of edges and g is a function called an incedence functions that assign to each edges e element of E, a one element subset {x} or a two element{v, w} where V and w are vertices.

Question 2

simple graph,

Answer 2

there is at most one edge between any two vertices, and there are no self-loops or multiple edges.

Question 3

complete graph

Answer 3

is a simple graph in which every pair of distinct vertices is connected by an edge.

Question 4

bipartite graph

Answer 4

is a graph whose vertices can be divided into two disjoint sets such that there are no edges between vertices within the same set.

Question 5

directed graph

Answer 5

, also known as a digraph, is a graph in which each edge has a direction associated with it.

Question 6

regular graph

Answer 6

is a graph in which each vertex has the same number of edges.

Question 7

walk

Answer 7

is a sequence of vertices and edges in a graph, where each edge connects two consecutive vertices in the sequence. The walk can traverse the same edge or vertex multiple times.

Question 8

directed walk

Answer 8

is a walk in a directed graph, where each edge has a specific direction associated with it.

Question 9

closed walk

Answer 9

is a walk that starts and ends at the same vertex.

Question 10

closed directed walk

Answer 10

is a closed walk in a directed graph, where the walk starts and ends at the same vertex and follows the direction of the edges.

Question 11

open walk

Answer 11

is a walk that starts and ends at different vertices. It can traverse the same edge or vertex multiple times but does not need to return to the starting vertex.

Question 12

open directed walk

Answer 12

is an open walk in a directed graph, where the walk starts and ends at different vertices and follows the direction of the edges.

Question 13

Trail:

Answer 13

is a walk in which no edge is repeated. It visits each vertex at most once but may revisit vertices.

Question 14

Path:

Answer 14

is a trail in which no vertex is repeated. It visits each vertex exactly once, except for the starting and ending vertices.

Question 15

Circuit:

Answer 15

is a closed trail in which no edge is repeated, except for the starting and ending vertex, which are the same.

Question 16

Cycle:

Answer 16

is a closed path in which no vertex is repeated, except for the starting and ending vertex, which are the same.

Question 17

subgraph

Answer 17

is a graph that is formed by selecting a subset of vertices and edges from a larger graph.

Question 18

Adjacent edges

Answer 18

In a graph, two edges are said to be adjacent if they share a common vertex.

Question 19

isolated vertex

Answer 19

is a vertex in a graph that has no edges connecting it to any other vertex in the graph.

Question 20

Hamiltonian path

Answer 20

is a path in a graph that visits every vertex exactly once.it does not have to start and end at the same vertex.

Question 21

Hamiltonian cycle

Answer 21

, also known as a Hamiltonian circuit, is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Question 22

Hamiltonian circuit

Answer 22

is another term for a Hamiltonian cycle. It refers to a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Question 23

Hamiltonian graph

Answer 23

is a graph that contains a Hamiltonian cycle. It is a graph in which there exists a cycle that visits every vertex exactly once.