Graph Theory

Question 1

DEFINE LINES

Answer 1

EDGES OR ARCS

Question 2

DEFINE NETWORK

Answer 2

GRAPH WITH NUMBERS LINKED TO EACH EDGE, NUMBERS MAY REFER TO TIME OR DISTANCE = WEIGHED GRAPH WHEN EACH EDGE HAS A VALUE

Question 3

DEFINE DEGREE OF VERTEX

Answer 3

NUMBER OF EDGES CONNECTED TO GRAPH

Question 4

DIRECTED GRAPH

Answer 4

GRAPH WITH DIRECTED EDGES AKA DIAGRAPH

Question 5

LOOP

Answer 5

EDGE CONNECTING VERTEX TO ITSELF

Question 6

SIMPLE GRAPH

Answer 6

GRAPH WITH NO LOOPS AND MAX ONE EDGE CONNECTS ANY PAIR OF VERTICES

Question 7

COMPLETE GRAPH

Answer 7

EVERY EDGE IS CONNECTED TO EVERY OTHER VERTEX

Question 8

BIPARTITE GRAPH

Answer 8

TWO SETS OF VERTICES WITH EDGES CONNECTING FROM ONE SET OF VERTICES TO THE OTHER

Question 9

TRAIL

Answer 9

SEQUENCE OF CONNECTED EDGES SUCH THAT THE SECOND VERTEX OF EACH EDGE IS THE FIRST VERTEX OF THE NEXT EDGE

Question 10

PATH

Answer 10

TRAIL WHERE NO VERTEX IS PASSED MORE THAN ONCE

Question 11

CLOSED TRAIL

Answer 11

TRAIL WITH THE SAME START AND END VERTICES

Question 12

CYCLE

Answer 12

CLOSED TRAIL WHERE ONLY START AND END VERTICES ARE THE SAME

Question 13

ORDER OR DEGREE

Answer 13

NUMBER OF EDGES MEETING THAT VERTEX

Question 14

HAMILTONIAN CYCLE

Answer 14

CYCLE THAT CONTAINS EVERY VERTEX OF AN EDGE (n-1)!/2 n=vertices

Question 15

EULERIAN GRAPH

Answer 15

CONNECTED GRAPH WITH CLOSED TRAIL CONTAINING EVERY EDGE PRECISELY ONCE without taking pen off paper have to go back to same vertices, order of vertices has to be even

Question 16

ADJACENCY MATRIX

Answer 16

MATRIX THAT REPRESENTS GRAPH EACH ROW AND COLUMN REPRESENTS VERTEX OF GRAPH AND NUMBER ON MATRIX GIVES NUMBER OF EDGES JOINING A PAIR OF VERTICES

Question 17

TREE

Answer 17

CONNECTED GRAPH WITH NO CYCLES

Question 18

SPANNING TREE

Answer 18

TREE THAT CONNECTS ALL VERTICES WITH NO CYCLES

Question 19

MINIMUM SPANNING TREE

Answer 19

SPANNING TREE WITH MINIMUM WEIGHT FOR A NETWORK

Question 20

DEFINE GRAPH

Answer 20

A FINITE NUMBER OF POINTS CONNECTED BY LINES (POINTS=VERTICES OR NODES)