Identify the Graph
A graph where every pair of vertices is connected.
What is a complete graph?
A path uses every edge exactly once and returns to the start.
What is an Euler circuit?
Which algorithm repeatedly selects the smallest edge that does not create a circuit?
What is Kruskal’s Algorithm?
The probability of rolling a 3 on a fair six-sided die.
What is 1/6 ?
Choosing captain and co-captain from 10 players is this type of counting problem.
What is a permutation?
Two events that cannot occur at the same time are called this.
What are mutually exclusive events?
A graph has vertices with degrees 2, 2, 4, 2, 2.
Is the graph connected enough to possibly contain an Euler circuit?
What is yes?
A connected graph has exactly two odd-degree vertices. What does it contain?
What is an Euler path?
Which algorithm always travels to the nearest unvisited vertex?
What is the Nearest-Neighbor Algorithm?
You flip a coin twice. What is the probability of getting two heads?
What is 1/4 ?
Choosing 3 pizza toppings from 12 toppings is this type of counting problem.
What is a combination?
If one event affects the probability of another event, the events are called this.
What are dependent events?
A graph contains all vertices and no circuits. What type of graph is it?
What is a tree?
A path visits every vertex exactly once but does not return home.
What is a Hamiltonian path?
In the Sorted-Edges Algorithm, this cannot happen at a vertex.
What is 3 used edges meeting at one vertex?
A bag contains 5 red and 3 blue marbles. One marble is selected. What is the probability of blue?
What is 3/8 ?
How many outcomes are possible when rolling two six-sided dice?
What is 36?
A graph requires at least 3 colors so that adjacent vertices have different colors. What is its chromatic number?
What is 3?
A graph has 7 vertices and every vertex has degree 6. What type of graph is this?
What is a complete graph?
True or False: A graph can have a Hamiltonian circuit without having an Euler circuit.
What is True?
A graph coloring uses 4 colors. What does this tell us about the chromatic number?
What is the chromatic number is at most 4?
A card is selected from a standard deck. What is the probability of selecting a king OR a queen?
What is 2/13 ?
A password consists of 2 letters followed by 3 digits. How many possible passwords are there if repetition is allowed?
What is 676,000?
A complete graph with 5 vertices is called this.
What is K5?
A graph has 6 vertices and 5 edges and is connected. What type of graph must it be?
What is a tree?
A connected graph has vertex degrees 2, 4, 3, 5, 2, 4.
Does it contain an Euler circuit, Euler path, or neither?
What is an Euler path?
Why can the Nearest-Neighbor Algorithm fail to produce the optimal Hamiltonian circuit?
What is choosing the nearest edge each time does not always give the smallest total cost?
A jar contains 4 green and 6 yellow marbles. Two marbles are selected without replacement. What is the probability both are green?
What is 2/15 ?
How many ways can 4 students be selected from a group of 10?
What is 210?
A graph has vertex degrees 1, 2, 2, 3, 4.
How many odd-degree vertices does the graph have?
What is 2?