CP 8 Graph Theory Flashcards
What is the criteria for a graph
Antireflexive and Symmetric
What is the formula for a graph
G=(Vg,Eg)
What is Vg in the graph formula
the vertices
what is Eg in the graph formula
Edges
If Vg={a,b,c,d} what could the Eg look like
Eg={{a,b},{a,c},{c,d},{d,a}
TF there can be more than one correct drawing of a graph
T
Given the edge {u,v} we say that u and v are _____ to eachother, we also say that u and v are ______ with the edge {u,v}
adjacent
incident
What another way of thinking about adjacent and incident
adjacent = theres a line connecting a and b
incident= if theres 2 lines connected to c, c is incident with 2 edges {a,c} and {c,d}
what is a connected graph
all elements must be connected (theres a path to any element)
what is a disconnected graph
not all elements are connected (cannot get to an element by a path)
what is a cycle
a path that starts and ends at the same vertex, with no repeated edges or vertices (except the starting and ending vertex
TF you can have a vertex appear twice in a path
F, every vertex can only appear once in a path
what is the criteria for a tree graph
A graph is a tree when it has no cycles, and it also must be connected
what is the degree of a vertex
how many lines are touching the vertex /going in or out if the vertex
(if a vertex has 2 lines touching it it has a degree of 2)
TF we can see that in a tree graph, every tree with n≥2 vertices has at least 1 vertex of degree 1
T
