Graph Theory Flashcards
DEFINE LINES
EDGES OR ARCS
DEFINE NETWORK
GRAPH WITH NUMBERS LINKED TO EACH EDGE, NUMBERS MAY REFER TO TIME OR DISTANCE = WEIGHED GRAPH WHEN EACH EDGE HAS A VALUE
DEFINE DEGREE OF VERTEX
NUMBER OF EDGES CONNECTED TO GRAPH
DIRECTED GRAPH
GRAPH WITH DIRECTED EDGES AKA DIAGRAPH
LOOP
EDGE CONNECTING VERTEX TO ITSELF
SIMPLE GRAPH
GRAPH WITH NO LOOPS AND MAX ONE EDGE CONNECTS ANY PAIR OF VERTICES
COMPLETE GRAPH
EVERY EDGE IS CONNECTED TO EVERY OTHER VERTEX
BIPARTITE GRAPH
TWO SETS OF VERTICES WITH EDGES CONNECTING FROM ONE SET OF VERTICES TO THE OTHER
TRAIL
SEQUENCE OF CONNECTED EDGES SUCH THAT THE SECOND VERTEX OF EACH EDGE IS THE FIRST VERTEX OF THE NEXT EDGE
PATH
TRAIL WHERE NO VERTEX IS PASSED MORE THAN ONCE
CLOSED TRAIL
TRAIL WITH THE SAME START AND END VERTICES
CYCLE
CLOSED TRAIL WHERE ONLY START AND END VERTICES ARE THE SAME
ORDER OR DEGREE
NUMBER OF EDGES MEETING THAT VERTEX
HAMILTONIAN CYCLE
CYCLE THAT CONTAINS EVERY VERTEX OF AN EDGE (n-1)!/2 n=vertices
EULERIAN GRAPH
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
ADJACENCY MATRIX
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
TREE
CONNECTED GRAPH WITH NO CYCLES
SPANNING TREE
TREE THAT CONNECTS ALL VERTICES WITH NO CYCLES
MINIMUM SPANNING TREE
SPANNING TREE WITH MINIMUM WEIGHT FOR A NETWORK
DEFINE GRAPH
A FINITE NUMBER OF POINTS CONNECTED BY LINES (POINTS=VERTICES OR NODES)
