Explanation Given: Five ships, the Arabella, Constantine, Drury, Egmont and Fungo, arrive at five loading docks. Each dock can only accept certain ships. Procedure used: Independent set algorithm Step 1 : Label each column containing no starred 1 . Step 2 : Scan and label Step 2.1 (Scan columns) For each column that is labeled but not scanned, look at every unstarred 1 in that column. If such a 1 is in an unlabeled row, then label that row with the name of the column being scanned. Mark the column to indicate that it has been scanned. Step 2.2 (Scan rows) For each row that is labeled but not scanned, look for a starred 1 in that row. If there is a starred 1 in the row, then label the column containing the starred 1 with the name of the row being scanned. Mark the row to indicate that it has been scanned. Repeat that above process until either some labeled row contains no starred 1 or all the labeled rows and all the labeled columns have been scanned. Step 3 : If possible enlarge the independent set. Step 3.1 Find the first labeled row that contains no starred 1 . Circle the 1 in this row and in the column that the row is labeled with. Circle the starred 1 in this column and the row that this column is labeled with. Then circle the unstarred 1 in this new row and in the column that this row is labeled with. Continue in this manner until a 1 is circled in a column labeled in step 1 . Step 3.2 : Reverse the stars on all the circled 1s. This gives an independent set of 1s with one more element than the original set. Step 3.3 : The present independent set is a maximum independent set. Calculation: It is given that Dock 1 can accept only the Constantine or Drury. Likewise, Dock 2 can only the Egmont or Fungo, Dock 3 the Constantine, Egmont or Fungo, Dock 4 the Arabella, Drury or Fungo and Dock 5 the Arabella, Constantine or Egmont. From the given information, the matrix obtained is shown below where Arabella, Constantine, Drury, Egmont and Fungo is represented by A , C , D , E and F respectively. A C D E F 1 2 3 4 5 [ 0 1 * 1 0 0 0 0 0 1 * 1 0 1 0 1 1 * 1 * 0 1 0 0 1 1 0 1 0 ] Label the unstarred column in the above matrix. A C D E F 1 2 3 4 5 [ 0 1 * 1 0 0 0 0 0 1 * 1 0 1 0 1 1 * 1 * 0 1 0 0 1 1 0 1 0 ] # Scan the labeled columns in the above matrix as shown below. A C D E F 1 2 3 4 5 [ 0 1 * 1 0 0 0 0 0 1 * 1 0 1 0 1 1 * 1 * 0 1 0 0 1 1 0 1 0 ] D D # √ Scan the labeled rows in the above matrix as shown below. A C D E F 1 2 3 4 5 [ 0 1 * 1 0 0 0 0 0 1 * 1 0 1 0 1 1 * 1 * 0 1 0 0 1 1 0 1 0 ] D √ D √ 4 1 # √ Scan the labeled columns in the above matrix as shown below

5th Edition

ISBN: 9780134689562

Author: Dossey, John A.

Publisher: Pearson,

See similar textbooks

Concept explainers

Addition Rule of Probability

It simply refers to the likelihood of an event taking place whenever the occurrence of an event is uncertain. The probability of a single event can be calculated by dividing the number of successful trials of that event by the total number of trials.

Expected Value

When a large number of trials are performed for any random variable ‘X’, the predicted result is most likely the mean of all the outcomes for the random variable and it is known as expected value also known as expectation. The expected value, also known …

Probability Distributions

Understanding probability is necessary to know the probability distributions. In statistics, probability is how the uncertainty of an event is measured. This event can be anything. The most common examples include tossing a coin, rolling a die, or choosi…

Basic Probability

The simple definition of probability it is a chance of the occurrence of an event. It is defined in numerical form and the probability value is between 0 to 1. The probability value 0 indicates that there is no chance of that event occurring and the prob…

Videos

Question

Chapter 6.3, Problem 23E

To determine

The maximum matching set with improvement by independent set algorithm.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 6.3, Problem 22E

Chapter 6.3, Problem 24E

Students have asked these similar questions

these are the questions and solutions. Please explain and show the method of the solutions

The evolution of a population of Hippos, R(t), in hundreds, time in years, in an African National Park is given by the equation, dR dt (a) Solve the system exactly for R(t). = R(7 – R); R(0) = 3 2 (b) What happens as the time t → ∞o, i.e. what is the population a long time in the future? (c) Write an Euler scheme and compute until the population levels off (using Excel, Matlab, Octave, LibreCalc or similar). Do it twice, once with At = 0.1 and once with At = 0.05. (d) Plot all of your solutions on the same set of axes and comment.

find For triangle ABC, with vertices A = (3,-1,2), B = (-5,4,-4) and C = (6, −1, −1), (a) the length of side AB, (b) the equation of the line that passes through A and B, (c) the angle at vertex B, (d) a vector perpendicular to the plane containing the triangle ABC, (e) the area of the triangle ABC. (f) the equation of a plane passing through A, B and C.

Chapter 6 Solutions

Discrete Mathematics

Ch. 6.1 - Prob. 1E Ch. 6.1 - Prob. 2E Ch. 6.1 - Prob. 3E Ch. 6.1 - Prob. 4E Ch. 6.1 - Prob. 5E Ch. 6.1 - Prob. 6E Ch. 6.1 - Prob. 7E Ch. 6.1 - Prob. 8E Ch. 6.1 - Prob. 9E Ch. 6.1 - Prob. 10E

Ch. 6.1 - Prob. 11E Ch. 6.1 - Prob. 12E Ch. 6.1 - Prob. 13E Ch. 6.1 - Prob. 14E Ch. 6.1 - Prob. 15E Ch. 6.1 - Prob. 16E Ch. 6.1 - Prob. 17E Ch. 6.1 - Prob. 18E Ch. 6.1 - Prob. 19E Ch. 6.1 - Prob. 20E Ch. 6.1 - Prob. 21E Ch. 6.1 - Prob. 22E Ch. 6.1 - Let S1, S2, … , Sm and T1, T2, … , Tn be sequences...Ch. 6.1 - Prob. 27E Ch. 6.1 - Prob. 28E Ch. 6.1 - Prob. 29E Ch. 6.1 - Prob. 30E Ch. 6.2 - Prob. 1E Ch. 6.2 - Prob. 2E Ch. 6.2 - Prob. 3E Ch. 6.2 - Prob. 4E Ch. 6.2 - Prob. 5E Ch. 6.2 - Prob. 6E Ch. 6.2 - Prob. 7E Ch. 6.2 - Prob. 8E Ch. 6.2 - Prob. 9E Ch. 6.2 - Prob. 10E Ch. 6.2 - Prob. 11E Ch. 6.2 - Prob. 12E Ch. 6.2 - Prob. 13E Ch. 6.2 - Prob. 14E Ch. 6.2 - Prob. 15E Ch. 6.2 - Prob. 16E Ch. 6.2 - Prob. 17E Ch. 6.2 - Prob. 18E Ch. 6.2 - Prob. 19E Ch. 6.2 - Prob. 20E Ch. 6.2 - Prob. 21E Ch. 6.2 - Prob. 22E Ch. 6.2 - Prob. 23E Ch. 6.2 - Prob. 24E Ch. 6.2 - Prob. 25E Ch. 6.2 - Prob. 26E Ch. 6.2 - Find a graph in which a maximum matching has fewer...Ch. 6.2 - Prob. 32E Ch. 6.3 - Prob. 1E Ch. 6.3 - Prob. 2E Ch. 6.3 - Prob. 3E Ch. 6.3 - Prob. 4E Ch. 6.3 - Prob. 5E Ch. 6.3 - Prob. 6E Ch. 6.3 - Prob. 7E Ch. 6.3 - In Exercises 5–10, a matrix is given with an...Ch. 6.3 - Prob. 9E Ch. 6.3 - Prob. 10E Ch. 6.3 - Prob. 11E Ch. 6.3 - Prob. 12E Ch. 6.3 - Prob. 13E Ch. 6.3 - Prob. 14E Ch. 6.3 - Prob. 15E Ch. 6.3 - Prob. 16E Ch. 6.3 - Prob. 17E Ch. 6.3 - Prob. 18E Ch. 6.3 - Prob. 19E Ch. 6.3 - Prob. 20E Ch. 6.3 - Prob. 21E Ch. 6.3 - Prob. 22E Ch. 6.3 - Prob. 23E Ch. 6.3 - Prob. 24E Ch. 6.4 - Prob. 1E Ch. 6.4 - Prob. 2E Ch. 6.4 - Prob. 3E Ch. 6.4 - Prob. 4E Ch. 6.4 - Prob. 5E Ch. 6.4 - Prob. 6E Ch. 6.4 - Prob. 7E Ch. 6.4 - Prob. 8E Ch. 6.4 - Prob. 10E Ch. 6.4 - Prob. 11E Ch. 6.4 - Prob. 12E Ch. 6.4 - Prob. 13E Ch. 6.4 - Prob. 14E Ch. 6.4 - Prob. 15E Ch. 6.4 - Prob. 16E Ch. 6.4 - Prob. 17E Ch. 6.5 - Prob. 1E Ch. 6.5 - Prob. 2E Ch. 6.5 - Prob. 3E Ch. 6.5 - Prob. 4E Ch. 6.5 - Prob. 5E Ch. 6.5 - Prob. 6E Ch. 6.5 - Prob. 7E Ch. 6.5 - Prob. 8E Ch. 6.5 - Prob. 9E Ch. 6.5 - Prob. 10E Ch. 6.5 - Prob. 11E Ch. 6.5 - Prob. 12E Ch. 6.5 - Prob. 13E Ch. 6.5 - Prob. 14E Ch. 6.5 - Prob. 15E Ch. 6 - Prob. 1SE Ch. 6 - Prob. 2SE Ch. 6 - Prob. 3SE Ch. 6 - Prob. 4SE Ch. 6 - Prob. 5SE Ch. 6 - Prob. 6SE Ch. 6 - Prob. 7SE Ch. 6 - Prob. 8SE Ch. 6 - Use the independent set algorithm to find a...Ch. 6 - Prob. 10SE Ch. 6 - Prob. 11SE Ch. 6 - Prob. 12SE Ch. 6 - Prob. 13SE Ch. 6 - Prob. 14SE Ch. 6 - Prob. 15SE Ch. 6 - Prob. 16SE Ch. 6 - Prob. 17SE

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.