Find a seating arrangement by showing the graph

Reference no: EM131177353

we consider a puzzle posed by Petkovi´c in [Pe09] (based on a problem in [AvCh80]). Suppose that King Arthur has gathered his 2n knights of the Round Table for an important council. Every two knights are either friends or enemies, and each knight has no more than n - 1 enemies among the other 2n - 1 knights. The puzzle asks whether King Arthur can seat his knights around the Round Table so that each knight has two friends for his neighbors

Suppose that are eight knights Alynore, Bedivere, Degore, Gareth, Kay, Lancelot, Perceval, and Tristan. Their lists of enemies are A (D, G, P), B (K, P, T), D (A, G, L), G (A, D, T), K (B, L, P), L (D, K, T), P (A, B, K), T (B, G, L), where we have represented each knight by the first letter of his name and shown the list of enemies of that knight following this first letter. Draw the graph representing these eight knight and their friends and find a seating arrangement where each knight sits next to two friends.

Reference no: EM131177353

Questions Cloud

What is grvt strategic intent : Your analysis should include: What is GRVT's strategic intent? What are GRVT's Vision, Mission and Values? Who are the stakeholders in GRVT? How does GRVT seek to position itself

Explain the basis of ultrasonic doppler flow meter : Use a suitable block diagram to explain the basis of ultrasonic Doppler flow meter and quote the necessary equations .

Thought-provoking digital marketing quotes : The data comes into the room from many sources, and you have to use that data like a modern-day orchestra leader, blending the inputs in real time in a combination that is as much an art as a science.

Design a circuit with the following given : design a circuit with the following:-- 3volts- 1.5v max charge- capacitor 1000 micro ferrand.

Find a seating arrangement by showing the graph : Draw the graph representing these eight knight and their friends and find a seating arrangement where each knight sits next to two friends.

Specific benefits that could be achieved with big data : Specific benefits that could be achieved with Big Data How problems of processing Big Data for home appliances would be overcome Benefits of offloading data processing to the cloud or a remote data centre

Find the bandwidths of these graphs : That is, the bandwidth is the minimum over all listings of the vertices of the maximum difference in the indices assigned to adjacent vertices. Find the bandwidths of these graphs

Probability density and cumulative probability function : Show the Probability density function and cumulative probability function of a sinusoidal random variable.

What is the intent of regulatory compliance : What is the intent of regulatory compliance, and what is the role of IT in maintaining corporate compliance? What can happen to organizations and their senior management if they ignore compliance mandates?

User Account

All Pages