Quiz 3

Graph Theory

Muhammad Ali
FA22-BCS-053
Section BCS-4B
Question: Write at least three real life applications of each of the three topics.
Answer:
Coloring:
• Scheduling: Imagine you have a bunch of classes to schedule, and some teachers can't teach two classes at once.
By turning this into a graph (classes are vertices, conflicts are edges), coloring the graph helps ensure no teacher
has classes scheduled at the same time.
• Wireless Networks: Cell phone towers can't use the same frequency if they're close together, causing
interference. Coloring a graph where towers are vertices and connections are edges helps assign frequencies
effectively.
• Timetabling Exams: Schools want to avoid scheduling exams for students taking related subjects at the same
time. Coloring a graph where exams are vertices and conflicts are edges helps create a feasible exam schedule.

Independent Sets:
• Scheduling classes to avoid conflicts: Imagine you're a course scheduler at a university. Each course is a vertex,
and an edge connects two courses if a student cannot take both due to scheduling conflicts (maybe they overlap or
require the same resources). An independent set in this scenario would be a group of courses that can all be
scheduled at the same time without any conflicts. Finding the maximum independent set would allow you to
schedule the maximum number of courses concurrently.
• Frequency assignment in radio communication: Imagine you have a bunch of radio towers that need to
transmit signals. Each tower is a vertex, and an edge is drawn between two towers if their frequencies are too
close and would interfere with each other. An independent set here would be a group of towers that can all use
their assigned frequencies simultaneously without causing interference. Finding the maximum independent set
would allow you to assign the maximum number of frequencies without any interference issues.
• Social distancing at a party: This one might be a bit more relatable! Imagine you have a social gathering, and
people are represented by vertices. An edge is drawn between two people if they live together or are close
contacts and should avoid proximity due to social distancing guidelines. An independent set in this scenario
would be a group of people who can safely stand near each other while maintaining social distance. Finding a
maximum independent set would allow the maximum number of people to gather in close proximity while
following social distancing rules.

Matching:
• Roommate Matching: Finding roommates can be tricky! Imagine a compatibility survey where students list
their preferences. We can create a graph where students are vertices and edges connect compatible pairs. A
matching algorithm can help find roommates who are most likely to get along, ensuring a harmonious living
situation.
• Resource Allocation: Think about a hospital with doctors and patients needing surgery. Doctors have different
specialties, and patients require specific procedures. A graph can represent doctors and patients with edges
indicating a doctor's qualification for a patient's surgery. A matching algorithm can help efficiently assign
patients to surgeons, ensuring everyone receives the care they need.
• Delivery Optimization: Delivery companies deal with a complex task of assigning drivers to routes. We can
create a graph where locations are vertices, and edges represent possible routes between them. A matching
algorithm can help find efficient routes for drivers, minimizing travel time and maximizing deliveries.

Vertex cover:
• Guard placement in a museum: Imagine a museum with a collection of valuable artifacts spread throughout the
exhibit halls. You want to place security guards strategically to ensure that every hallway or room containing
artifacts is within sight of at least one guard. In this scenario, the museum layout can be modeled as a graph,
where vertices represent rooms/halls and edges represent connections between them. Finding a minimum vertex
 cover in this graph would correspond to placing the minimum number of guards such that every artifact
(represented by an edge) is "guarded" by a guard (represented by a vertex in the cover).
• Facility location problem: Imagine a company that needs to build warehouses to distribute goods to various
retail stores across a city. The goal is to minimize the number of warehouses needed while ensuring that every
store can be serviced by at least one warehouse. This can be modeled as a graph where vertices represent potential
warehouse locations and edges represent connections between cities. Finding a minimum vertex cover in this
graph would give the optimal placement of warehouses such that every store (represented by an edge) is reachable
from at least one warehouse (represented by a vertex in the cover).
• Social network analysis: In social networks, a vertex cover can be used to identify a group of influential users
who can spread information effectively across the network. Here, the graph represents the social network, with
vertices representing users and edges representing connections (e.g., friendships). A vertex cover in this case
would be a group of influential users (vertices) who are connected to a large portion of the network (edges). By
targeting these users to spread information, it can be done more efficiently.

Edge Cover:
• Scheduling Exams: Imagine you have a school with several exams to be scheduled. Each exam can only be given
once, and no student can take two exams at the same time. This can be modeled as a graph where vertices
represent exams and edges connect exams that cannot be scheduled together (because they have common
students). An edge cover in this scenario would be a set of exams that can be scheduled without any conflicts.
Finding a minimum edge cover would correspond to scheduling the maximum number of exams simultaneously.
• Delivery Routes: A delivery company has a set of packages to deliver to different locations. A truck can only
carry a limited number of packages at once. We can model this situation as a graph where vertices represent
locations and edges connect locations that cannot be visited on the same trip (due to truck capacity limitations).
An edge cover here would be a set of deliveries that can be done using one truck each. Finding a minimum edge
cover would correspond to minimizing the number of trucks needed to deliver all packages.
• Sensor Placement: In a building, you want to place security sensors to cover all areas. Each sensor has a limited
range. We can model this scenario as a graph where vertices represent locations within the building and edges
connect locations that are within the range of a single sensor. An edge cover here would be a set of sensors that
collectively cover the entire building. Finding a minimum edge cover would correspond to using the minimum
number of sensors to achieve complete coverage.

Dominating Set:
• Security Guard Placement: Imagine a museum layout modelled as a graph, where vertices represent rooms and
edges represent doorways connecting them. A dominating set in this scenario would be a minimal set of rooms
where security guards can be placed to ensure they can visually cover (dominate) all the other rooms in the
museum. This helps security teams strategically position guards to deter theft or ensure visitor safety with
minimal manpower.
• Sensor Network Design: Wireless sensor networks can be modelled by graphs, where sensor nodes are vertices
and communication links between them are edges. When designing such a network, you'd ideally want every area
to be within the sensing range of at least one sensor. Finding a dominating set in this case would correspond to
finding the minimum number of sensors needed to ensure complete coverage of the monitored area.
• Cell Tower Placement: In cellular networks, cell towers can be represented as vertices in a graph, connected by
edges if they can communicate with each other. A dominating set here would represent a set of towers that
provide signal coverage to all areas within the network. This helps telecommunication companies strategically
place cell towers to optimize network coverage while minimizing infrastructure costs.