My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 2nd, 2015, 08:00 AM   #1
Newbie
 
Joined: Oct 2015
From: Poland

Posts: 1
Thanks: 0

Find max size of clique in permutation graph

Hello,

I have following problem. I have following graph:
1 3
1 5
1 4
2 4
2 3
2 5
3 4

which looks like below


I want to calculate permutation for this graph. My result is:
(4 3 5 1 2)

But it looks that is wrong answer.

Size of the largest clique in permutation graph is equal to the longest decreasing subsequence of permutation.
The longest decreasing subsequence of my permutation is 2, when the largest clique has size equals to 3.

Could you please help me with this issue?

I would appreciaty any help that you can provide.

Best regards
Antek
Antek is offline  
 
October 2nd, 2015, 06:32 PM   #2
Senior Member
 
Joined: Oct 2013
From: New York, USA

Posts: 632
Thanks: 85

I'm not sure I understand the question. If by permutations you mean how many line segments met each point, just count the frequency of each number in the original list, making the answer (3 3 3 3 2).
EvanJ is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

Tags
clique, find, graph, max, permutation, size



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Find size of projected image using distances Kamster Geometry 0 April 22nd, 2014 09:42 PM
Set size is relative - Same topology of negative size sets BenFRayfield Applied Math 4 December 21st, 2013 11:58 PM
Find the Mafia!: an iOS game on the maximum clique problem experiware Applied Math 1 June 17th, 2013 01:52 PM
find an inverse of a permutation cycle rayman Abstract Algebra 5 January 29th, 2012 02:26 AM
Number of ways to make a graph from n-size vertex set Singularity Applied Math 1 April 15th, 2011 07:42 AM





Copyright © 2019 My Math Forum. All rights reserved.