Graph Thoery

Question 1

Connected graph

Answer 1

All vertices directly or indirectly connected

Question 2

Simple graph

Answer 2

no loops or multiple edges

Question 3

tree

Answer 3

connected graph with no circuits

Question 4

undirected graph

Answer 4

Weight of A-B = B-A. If loop/multiple edge is present graph is directed

Question 5

weight of an edge

Answer 5

any factor ascribed to the edge

Question 6

order

Answer 6

number of vertices in the graph

Question 7

degree of a vertex

Answer 7

number of edges leading to/from that vertex

Question 8

Regular graph

Answer 8

all vertices of same degree

Question 9

circuit

Answer 9

a path that starts and ends at same vertex

Question 10

path

Answer 10

route between 2 specified vertices so that no edge used more than once, not all edges need to be used. starting point not usually endpoint.

Question 11

size

Answer 11

total number of edges

Question 12

Adjacent vertices

Answer 12

directly connected by a common edge

Question 13

Neighborhood of a vertex

Answer 13

vertices that are connected to a vertex

Question 14

girth

Answer 14

sum of weight of edges

Question 15

planar graph

Answer 15

drawn without touching

Question 16

formula for degree of regular graph

Answer 16

degree = order-1

Question 17

formula for size of complete graph

Answer 17

1/2*order(order-1)

Question 18

Isomorphic graphs

Answer 18

Same size, order + neighborhood. Test to see how many hops it takes to get back to a starting vertex.

Question 19

Eulerian path

Answer 19

every edge once, starts and ends at different vertices, vertices can be visited more than once. Must begin and end at the pair of odd vertices. Only exists if there is 1 pair of vertices of odd degree

Question 20

Eulerian circuit

Answer 20

every edge once, starts and ends at same vertex, vertices may be visited more than once. Only exists if no vertices of odd degree

Question 21

Hamiltonian circuit

Answer 21

each vertex once before returning to starting vertex, doesn’t need to use every edge.

Question 22

circuit

Answer 22

a path that starts and ends at same vertex