D1 - definitions

Question 0

DEFINE: Degree/Valency/Order of a vertex

Answer 0

the number of edges incident to it

Question 1

DEFINE: Subgraph

Answer 1

a graph each of whose edges and vertices belong to the original graph. ( a part of a graph )

Question 2

DEFINE: A Path

Answer 2

Finite sequence of edges that the end vertex of one edge is the start vertex of the next and no vertex appears more than once

Question 3

DEFINE: A walk

Answer 3

a path where you are permitted to return to vertices more than once

Question 4

DEFINE: Cycle

Answer 4

A closed path, the end vertex of the last edge is the start vertex of the first edge

Question 5

DEFINE: Connected Graph

Answer 5

It is a connected if a path can be found between any two vertices

Question 6

DEFINE: A loop

Answer 6

Is a edge that starts and finishes at the same vertex

Question 7

DEFINE: A simple Graph

Answer 7

A graph where there are no loops and have no more than one edge connecting any pair of vertices

Question 8

DEFINE: Digraph

Answer 8

A graph with directed edges ( the edges have a direction associated with them

Question 9

DEFINE: A Tree

Answer 9

a connected graph with no cycles

Question 10

DEFINE: Spanning tree

Answer 10

is subgraph which includes all vertices of the original graph and is also a tree

Question 11

DEFINE: Bipartite Graph

Answer 11

A GRAPH consisting of two sets of vertices X and Y the edges only join a vertex in X with a vertex in Y not vertices within it’s set

Question 12

DEFINE: A Complete Graph

Answer 12

A graph in which every vertex is directly connected by a edge to each other vertex

Question 13

DEFINE: Isomorphic graph

Answer 13

Graphs that show the same information but are drawn differently

Question 14

DEFINE: Weighted graph

Answer 14

a graph with numbers associated with each edge

Question 15

DEFINE: Adjacency matrix

Answer 15

record the number of direct links between vertices

Question 16

DEFINE: Distance Matrix

Answer 16

Records the weight on the edges where there is no weight this is indicated by a ‘-‘

Question 17

DEFINE: MST Minimum Spanning tree

Answer 17

is a spanning tree such that the total length of it’s arcs is as small as possible, some times called a minimum connector

Question 18

DEFINE: Eulerian graph

Answer 18

A graph with all even valencies

Question 19

DEFINE: Semi Eulerian Graph

Answer 19

If two valencies are odd, and the rest even

Question 20

DEFINE: Traversable

Answer 20

If it is possible to go through every arc once without taking your pen from the paper

Question 21

DEFINE: Matching

Answer 21

a matching is the 1 to 1 pairing of some or all of the elements in set x with a element of set Y

Question 22

DEFINE: Maximal matching

Answer 22

a matching in which the number of arcs is as large as possible

Question 23

DEFINE: Complete Matching

Answer 23

A complete matching had n arcs, if both sets have n nodes

Question 24

DEFINE: Alternating Path

Answer 24

an alternating path starts at a unmatched node on one side of the Bipartite graph and finishes and a unmatched node on the other side, using arcs that alternately not in and in the initial matching