Graph Theory

Question 1

Planar Graph

Answer 1

No edges intersect or corss except at vertices

Question 2

Faces

Answer 2

outside is also a face

Question 3

Euler’s formula

Answer 3

v-e+f=2

Question 4

What is a walk

Answer 4

Sequence of edges

Question 5

open walk

Answer 5

walk that starts and finish at different vertices

Question 6

Closed walk

Answer 6

Walk that starts and finishes at same vertex

Question 7

What is trail

Answer 7

trail is walk with no repeated edges

Question 8

Closed trail

Answer 8

trail that starts and ends at same vertex

Question 9

What is a path

Answer 9

Path is walk with no repeated edges and no repeated vertices

Question 10

Open path

Answer 10

Path is walk with no repeated edges and no repeated vertices and doesnt end at same vertices

Question 11

Closed path

Answer 11

Path is walk with no repeated edges and no repeated vertices and end at same vertices

Question 12

What is a cycle

Answer 12

cycle is path with no repeated edges and no repeated vertices that start and end at same vertex. Important that no repeated stuff except for start and end vertices

Question 13

What is a transversible graph and rules

Answer 13

has trail that includes every edge, rules 2 vertices odd or everything even.

Question 14

What is a eulerian graph

Answer 14

Eulerian if it has closed trail that includes every edge nonly once. to be eulerian graph must be connected and havel all vertices to be even degree

Question 15

What is semi elulerian

Answer 15

has open trail that includes every edge only once. to be semi eulerian graph must be connected, have exactly 2 odd vertices. Eulerian trail must start and finish at odd dgrees

Question 16

Hamiltonian path

Answer 16

involves all vertices but not neccessarily all edges.

Question 17

Djikistra algorithm

Answer 17

shortrst route between 2 vertices

Question 18

Hamiltonian cycle

Answer 18

Hamiltonian path that starts and finishes at same vertices

but note that Hamiltonian cycle does not have to involve all edges

Question 19

What is transversible graph

Answer 19

A traversable graph has a trail that includes every edge in the graph

Question 20

Rules for tansversable graph

Answer 20

must be connected,
all vertices are of even degree; or
exactly two vertices are of odd degree and the rest are of even degree.
a traversable graph will have either a trail (open or closed) or a cycle that involves the
use of every edge in the graph

Question 21

Is a grapg more than two vertices transversible

Answer 21

no

Question 22

What is a Eulerian Graph

Answer 22

s Eulerian if it has a closed trail that includes every edge once only, To be Eulerian, a graph must:
be connected
have all vertices of an even degree.
An Eulerian graph can start at any vertex and will also finish at that vertex.

Question 23

What is a Semi Eulerian Graph

Answer 23

s semi-Eulerian if it has an open trail that includes every edge
once only. The trail in an Eulerian graph is called an Eulerian trail.To be semi-Eulerian, a graph must:
be connected.
have exactly two vertices of an odd degree.
An Eulerian trail must start at one of the odd degree vertices and will finish at the other
odd degree vertex.
Hint: Remember that Eulerian graphs a

Question 24

What is a Hamiltonian Path

Answer 24

h involves all the vertices but not
necessarily all the edges

Question 24

Conditions to ve semi eulerian

Answer 24

To be semi-Eulerian, a graph must:  be connected.  have exactly two vertices of an odd degree. An Eulerian trail must start at one of the odd degree vertices and will finish at the other odd degree vertex. Hint: Remember that Eulerian graphs a

Question 25

What is Hamiltonian Cycle

Answer 25

Hamiltonian cycle is a Hamiltonian path that starts and finishes at the same vertex.

Question 26

Weighted Graph

Answer 26

A weighted graph is a graph where a number is associated with each edge. These numbers are called weights.

Question 27

Network

Answer 27

weighted graph in which the weights are physical quantities, for example, distance, time, cost

Question 28

Disconnected graph

Answer 28

A disconnected graph has at least one pair of vertices between which there is no path.

Question 29

Simple Grpah

Answer 29

a graph that does not have loops and does not have multiple edges.

Question 30

Complete graph

Answer 30

A complete graph has every vertex connected to every other vertex by an edge.

Question 31

Subgrapg

Answer 31

ubgraph is a graph that is part of a larger graph and has some of the same vertices and edges as that larger graph

Question 32

What is a bridge

Answer 32

A bridge is a single edge in a connected graph that if removed leaves the graph disconnected.