Fdtxjr

How to install cross-compiler on Ubuntu 18.04?

Unlock My Phone! February 2018

What is an equivalently powerful replacement spell for the Yuan-Ti's Suggestion spell?

Is it possible to map the firing of neurons in the human brain so as to stimulate artificial memories in someone else?

ssTTsSTtRrriinInnnnNNNIiinngg

How dangerous is XSS

My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?

Is this answer explanation correct?

What are the G forces leaving Earth orbit?

How can saying a song's name be a copyright violation?

Are British MPs missing the point, with these 'Indicative Votes'?

Theorists sure want true answers to this!

Finding the error in an argument

Avoiding the "not like other girls" trope?

What's the meaning of "Sollensaussagen"?

In Bayesian inference, why are some terms dropped from the posterior predictive?

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

Does int main() need a declaration on C++?

What historical events would have to change in order to make 19th century "steampunk" technology possible?

How to find if SQL server backup is encrypted with TDE without restoring the backup

How to show a landlord what we have in savings?

How seriously should I take size and weight limits of hand luggage?

How to stretch the corners of this image so that it looks like a perfect rectangle?

Where would I need my direct neural interface to be implanted?

Modeling problems using graphs

Modeling a (rather silly) magnet problem using graphsAdding metric to matroids in order to describe graphs whose vertices are points in Euclidean spaceConnectivity of random graphsRelabelling players in a tournamentHow to model a real-world graphical structure into a mathematical formulation?Average Total Time between EventsOn the chess board few squares are marked. Showthat the minimal number of ranks and files which cover all markedModel selectionTeam Ranking Model vs Graph Theory ModelLearning generative models of graphs

0

$begingroup$

I was wondering how can I learn how to model problems using some classical models in graph theory (graph coloring, vertex cover, matching, maximum cliques, independent sets and so on)
For example, I want to learn how to model the following problems :

1. Can we "cut" without lifting the pencil every edge in the following figure. We must pass once and only once through each edge ? (Hint : use a graph model)




2. Mr. Dupont wants to rent his apartment for a given period. She received several offers. Every proposition has a price and a period. Model this problem using a graph structure.




3. Chess : How to place 8 queens on a chess board so that no two queens threaten each other? How many queens do we need so that they control all of the squares? Can a knight run throw all of the squares while passing from each square once and only once?




4. Schedule : Assume we have $k$ teams ($k$ is an even number). Each team must play with each other team twice ( $2 times (k-1) = 2k-2$ parties)
   How to determine a valid affectation (using a graph-based model).
   How to modify the problem to respect the following constraint : Some parties cannot occur simultaneously**




5. Frequencies : A phone operator wants to dynamically allocate frequencies to users.
   If two users are using the same frequency in the same zone, we could have some technical issues.
   How to allocate frequencies in a way such that a third user cannot be in the same zone as two users with the same frequency. We want to minimize the number of frequencies used.
   We assume that users don't move.

N.B: I am not looking for answers to those questions, I am looking for references(books/ online courses; lecture notes etc.) that can teach me how to model similar problems using graph structures and classic models

graph-theory book-recommendation mathematical-modeling

share|cite|improve this question

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I would say that these problems are classic and well-studied, so almost every good book on graph theory would be appropriate. Personally, I recommend you two books: "Introduction to Algorithms" by Thomas H. Cormen for studying algorithms on graphs and Graph theory by F. Harary for non-algorithmic part of graph theory.
  $endgroup$
  – Vladislav
  Mar 20 at 21:22
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've took alook at Harary's book don't think it focuses on the modeling part though
  $endgroup$
  – Hilbert Hotel
  Mar 21 at 21:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can find most of these on youtube from memory . but they don't graph it. I think I could turn these into graphs though.
  $endgroup$
  – Roddy MacPhee
  Mar 22 at 0:25
  
  

  
  
  
  

add a comment | 

0

$begingroup$

I was wondering how can I learn how to model problems using some classical models in graph theory (graph coloring, vertex cover, matching, maximum cliques, independent sets and so on)
For example, I want to learn how to model the following problems :

1. Can we "cut" without lifting the pencil every edge in the following figure. We must pass once and only once through each edge ? (Hint : use a graph model)




2. Mr. Dupont wants to rent his apartment for a given period. She received several offers. Every proposition has a price and a period. Model this problem using a graph structure.




3. Chess : How to place 8 queens on a chess board so that no two queens threaten each other? How many queens do we need so that they control all of the squares? Can a knight run throw all of the squares while passing from each square once and only once?




4. Schedule : Assume we have $k$ teams ($k$ is an even number). Each team must play with each other team twice ( $2 times (k-1) = 2k-2$ parties)
   How to determine a valid affectation (using a graph-based model).
   How to modify the problem to respect the following constraint : Some parties cannot occur simultaneously**




5. Frequencies : A phone operator wants to dynamically allocate frequencies to users.
   If two users are using the same frequency in the same zone, we could have some technical issues.
   How to allocate frequencies in a way such that a third user cannot be in the same zone as two users with the same frequency. We want to minimize the number of frequencies used.
   We assume that users don't move.

N.B: I am not looking for answers to those questions, I am looking for references(books/ online courses; lecture notes etc.) that can teach me how to model similar problems using graph structures and classic models

graph-theory book-recommendation mathematical-modeling

share|cite|improve this question

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I would say that these problems are classic and well-studied, so almost every good book on graph theory would be appropriate. Personally, I recommend you two books: "Introduction to Algorithms" by Thomas H. Cormen for studying algorithms on graphs and Graph theory by F. Harary for non-algorithmic part of graph theory.
  $endgroup$
  – Vladislav
  Mar 20 at 21:22
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've took alook at Harary's book don't think it focuses on the modeling part though
  $endgroup$
  – Hilbert Hotel
  Mar 21 at 21:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can find most of these on youtube from memory . but they don't graph it. I think I could turn these into graphs though.
  $endgroup$
  – Roddy MacPhee
  Mar 22 at 0:25
  
  

  
  
  
  

add a comment | 

$begingroup$

I was wondering how can I learn how to model problems using some classical models in graph theory (graph coloring, vertex cover, matching, maximum cliques, independent sets and so on)
For example, I want to learn how to model the following problems :

1. Can we "cut" without lifting the pencil every edge in the following figure. We must pass once and only once through each edge ? (Hint : use a graph model)




2. Mr. Dupont wants to rent his apartment for a given period. She received several offers. Every proposition has a price and a period. Model this problem using a graph structure.




3. Chess : How to place 8 queens on a chess board so that no two queens threaten each other? How many queens do we need so that they control all of the squares? Can a knight run throw all of the squares while passing from each square once and only once?




4. Schedule : Assume we have $k$ teams ($k$ is an even number). Each team must play with each other team twice ( $2 times (k-1) = 2k-2$ parties)
   How to determine a valid affectation (using a graph-based model).
   How to modify the problem to respect the following constraint : Some parties cannot occur simultaneously**




5. Frequencies : A phone operator wants to dynamically allocate frequencies to users.
   If two users are using the same frequency in the same zone, we could have some technical issues.
   How to allocate frequencies in a way such that a third user cannot be in the same zone as two users with the same frequency. We want to minimize the number of frequencies used.
   We assume that users don't move.

N.B: I am not looking for answers to those questions, I am looking for references(books/ online courses; lecture notes etc.) that can teach me how to model similar problems using graph structures and classic models

graph-theory book-recommendation mathematical-modeling

share|cite|improve this question

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

$endgroup$

share|cite|improve this question

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

share|cite|improve this question

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233

asked Mar 20 at 19:55

Hilbert HotelHilbert Hotel

233