Math Is Fun Forum

aloha

Member

Registered: 2010-12-02

Posts: 13

Graph theory - Math

Hi, I need to solve this math problem. I'm in serious troubles , so I want to ask, that some body can't help me. Thx a lot!

Graph theory
Business travelers will have the task to visit all the cities in the region (all the vertices of the graph) exactly once and return back.

    * A) How many ways there is a traveling salesman in the complete graph Kn?
    * B) How many ways there is a traveling salesman in the complete graph minus one edge? (We denote such a graph Kn-xy, where xy is any strongly selected edge of a complete graph.)

Notes: There are the order of visited cities, and starting city! For example, the graph K3, there are 6 such different paths.

....Excuse my English

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Graph theory - Math

Hi aloha;

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

Below is K3. To get to all the cities marked A, B, C, starting with A and to return to A. I count 2 paths.

(Note: I am going to use the implies symbol ⇒ in this context to mean "to" )

A ⇒ B ⇒ C ⇒ A     Cost = 66

A ⇒ C ⇒ B ⇒ A     Cost = 66

If you do not have to return to A then there is only one.

A ⇒ C ⇒ B            Cost = 35

To understand what is meant by a hamiltonian cycle and path, go here.

http://en.wikipedia.org/wiki/Hamiltonian_cycle

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

aloha

Member

Registered: 2010-12-02

Posts: 13

Re: Graph theory - Math

Thank you for your help
Then I will resolve the last example ....Anybody solve it please? Thanks a lot

B) How many ways there is a traveling salesman in the complete graph minus one edge? (We denote such a graph Kn-xy, where xy is any strongly selected edge of a complete graph.)