Solving the Tropical Fish Tank Assignment Puzzle
Assigning tropical fish into tanks
Assigning tropical fish into tanks
Presented by,
Manisha Reddy Podduturi
Plan for the talk:
•
Tropical fish Problem
•
Real-World problem
•
Graph Construction
•
Special property
•
Problem solution
Tropical Fish Problem
A tropical fish hobbyist had six different types of fish:
Alphas, Betas, Cartas, Deltas, Epsalas and Fetas which shall
be designated by A, B, C, D, E and F respectively.
Real-World Problem:
Because of Predator-prey relationships, water conditions
and size only few fishes can be kept in the same tank.
What is the least number of tanks needed to place all the
fish?
Consider the following table shows which
fish cannot be together:
Graph Construction:
Can you figure out what each vertex and each edge
represent?
Here, each vertex represents one of the type of fish and
each edge connects vertices that are not compatible.
Interval Graph:
The problem turns out to be interval graph problem.
A
B
C
D
E
F
The interval graph shows the intersecting interval on a real
line. It has one vertex for each interval in the family and an
edge between every pair of vertices corresponding to
intervals that intersect.
Special Property:
Umbrella-Free Ordering
For every interval graph there will be an umbrella free ordering.
It states that, arranging the vertices in an order such that if there
is an edge between two vertices then any edge that lies
between the two vertices must be adjacent to the right vertex
in the ordering.
G has umbrella-free ordering if their exists an ordering of
vertices of G v1, v2, …. vn such that
a<b<c and a~c
⇒
b~c.
Umbrella-Free Ordering:
Problem Solution:
Graph Coloring:
It’s the simplest
form
, it is a way of coloring the vertices of a
graph such that no two adjacent vertices share the same
colour.
After coloring the graph using UFO:
1
Red
Blue
Green
Red
Blue
Green
Problem Solution:
What does each colour on the graph represent?
How Chromatic number help to solve the problem?
Several different combinations of fish are possible
depending on how the graph is coloured.
Fish with vertices of the same colour go in to the same
tank.
The fewest number of tanks the tropical fish owner will
need is three.
Dive into the challenge of assigning tropical fish into tanks efficiently based on predator-prey relationships, water conditions, and compatibility. Explore the graph theory approach to determine the minimum number of tanks needed, construct a graph representing fish compatibility, identify the problem as an interval graph, and discover the special property of umbrella-free ordering for interval graphs. Unravel the solution step by step for a fascinating fish tank assignment problem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Assigning tropical fish into tanks Presented by, Manisha Reddy Podduturi
Plan for the talk: Tropical fish Problem Real-World problem Graph Construction Special property Problem solution
Tropical Fish Problem A tropical fish hobbyist had six different types of fish: Alphas, Betas, Cartas, Deltas, Epsalas and Fetas which shall be designated by A, B, C, D, E and F respectively. Real-World Problem: Because of Predator-prey relationships, water conditions and size only few fishes can be kept in the same tank. What is the least number of tanks needed to place all the fish?
Consider the following table shows which fish cannot be together: Type A B C D E F Cannot be with B, C A, C, D A, B, D, E C, E, F C, D, F D, E
Can you figure out what each vertex and each edge represent? Here, each vertex represents one of the type of fish and each edge connects vertices that are not compatible.
Interval Graph: The problem turns out to be interval graph problem. A B C D E F The interval graph shows the intersecting interval on a real line. It has one vertex for each interval in the family and an edge between every pair of vertices corresponding to intervals that intersect.
Special Property: Umbrella-Free Ordering For every interval graph there will be an umbrella free ordering. It states that, arranging the vertices in an order such that if there is an edge between two vertices then any edge that lies between the two vertices must be adjacent to the right vertex in the ordering. G has umbrella-free ordering if their exists an ordering of vertices of G v1, v2, . vn such that a<b<c and a~c b~c.
Problem Solution: Graph Coloring: It s the simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same colour. After coloring the graph using UFO: 1 Red Blue Green Red Blue Green
Problem Solution: What does each colour on the graph represent? How Chromatic number help to solve the problem?
Several different combinations of fish are possible depending on how the graph is coloured. Fish with vertices of the same colour go in to the same tank. The fewest number of tanks the tropical fish owner will need is three. Tank 1 Tank 2 Tank 3 Alphas and Deltas Fetas and Cartas Betas and Epsalas
http://mitosystems.com/wp-content/uploads/2013/06/question-mark-300x300.jpghttp://mitosystems.com/wp-content/uploads/2013/06/question-mark-300x300.jpg
