Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
19 Cards in this Set
- Front
- Back
|
What is a 'walk'? |
- A route through a graph, passing through nodes and along arcs - A single node can be visited multiple times |
|
|
What is a 'path'? |
- Similar to a walk - A single vertex can only be visited once |
|
|
What is a 'trail'? |
- Similar to a walk - A single arc can only be visited once |
|
|
What is an Eulerian circuit? |
A trail that visits every arc and ends on the same vertex that it started on. |
|
|
What is a cycle? |
- Similar to a path - Starts and ends on the same vertex |
|
|
What is a Hamiltonian cycle? |
A cycle that visits all nodes |
|
|
What does it mean if nodes are 'connected'? |
The two nodes are connected directly or indirectly by arcs. |
|
|
What is connected graph? |
A graph where all nodes are connected. You can create a path between any two nodes. |
|
|
What is a loop? |
A arc that leads directly back to the node it started on |
|
|
What makes a graph simple? |
If there are no loops, and there is only one arc connecting any two nodes. |
|
|
What do you call a graph that has direction to it's arcs? |
A digraph |
|
|
What is the relation between: 1. The sum of the degrees of all nodes 2. The total number of arcs? |
Sum of degrees = (No. of arcs * 2) |
|
|
What is the degree of a node? |
The total number of arcs coming out of the node. Note: A loop counts as two arcs coming out of the node |
|
|
What is a tree? |
A connected graph with no cycles |
|
|
What is a spanning tree? |
A subgraph that is a tree and connects to all nodes. |
|
|
What is a subgraph? |
A section of a graph. |
|
|
What is a complete graph? |
A graph in which every node is connected to every other node. The total number of arcs can be written as 0.5n^(2)-0.5n, where n is the number of nodes. |
|
|
What is an isomorphic graph? |
Isomorphic graphs showing the same information, but are arranged differently. |
|
|
What is a planar graph? |
A graph that can be drawn without any arcs crossing overs is planar. |
