Graphs Flashcards
Simple graphs have no
Loops or duplicate arcs
A graph is connected if
A node is connected to every other node by a series of arcs.
A trail is
A route along connected arcs
How many arcs does a tree with x nodes have?
x-1
What is a closed trail?
A trail where the start and end nodes are the same.
What is a cycle?
A closed trail where ONLY the start and end nodes are visited more than once.
Will a graph have an even or odd number of odd nodes?
Even
What is an Eulerian graph?
A connected graph with a closed trail containing each arc once
What is the order of all nodes of an Eulerian graph- even or odd?
Even
What is a semi-eulerian graph?
An unclosed trail containing each node once.
How many odd nodes does a Semi-Eulerian graph have?
2
What is a tree?
A graph with no cycles
A path is a trail where
No arc is visited more than once
What is a planar graph?
A graph where the arcs do not cross.
A complete graph is one where…
Every node is connected to every other node
