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?
This 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 that has exactly two odd-degree vertices contains this.
What is an Euler path?
This algorithm always travels to the nearest unvisited vertex.
What is the Nearest-Neighbor Algorithm?
The probability of getting two heads if you flip a coin twice.
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, no vertex can have more than this number of used edges.
What is 2?
The probability of blue if one marble is selected from a bag that contains 5 red and 3 blue marbles.
What is 3/8 ?
The number of outcomes that are possible when rolling two six-sided dice.
What is 36?
A graph can be colored using 3 colors, but cannot be colored using only 2. This is its chromatic number.
What is 3?
This 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?
The smallest number of colors needed to color a graph so that adjacent vertices have different colors.
What is the chromatic number?
The probability of selecting a king OR a queen if a card is selected from a standard deck.
What is 2/13 ?
The number of passwords possible if a password consists of 2 letters followed by 3 digits and 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?
The Nearest-Neighbor Algorithm is used to find an approximation of this type of circuit.
What is a Hamiltonian circuit?
The probability both are green if two marbles are selected without replacement from a jar that contains 4 green and 6 yellow marbles.
What is 2/15 ?
The number of ways can 4 students be selected from a group of 10.
What is 210?
The number of odd-degree vertices of a graph that has vertex degrees 1, 2, 2, 3, 4.
What is 2?