Opened 6 years ago
Closed 6 years ago
#17532 closed PLEASE CHANGE (worksforme)
Convexity properties on graphs works incorrectly
Reported by: | azi | Owned by: | azi |
---|---|---|---|
Priority: | trivial | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Completely fixed; Fix reported upstream | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Hello!
It appears that the convexity properties module gives incorrect results. The hull (geodetic) number of the Petersen graph is 4 while Sage says it is 3.
sage: G.convexity_properties().hull_number(value_only=false) [4, 7, 8] sage: G.convexity_properties().hull([4,7,8]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
I have implemented a corrected version of the hull number algorithm that I believe to be faster as well. I'd suggest we make these two function part of the graph class instead of having a separate convexity module.
What do you guys think?
Change History (12)
comment:1 Changed 6 years ago by
comment:2 follow-up: ↓ 3 Changed 6 years ago by
I have verified the result in 4ways
- By implementing a different algorithm and getting 4 as an answer
- By drawing the solution given by sage and seeing that it does not give the whole graph
- Arguing as follows. In the Petersen graph any pair of vertices is connected by a UNIQUE shortest path and has diameter 2. Hence 3 vertices give you a hull of size at most 3+ (3 \choose 2)*1 = 9
- By checking this paper http://ajc.maths.uq.edu.au/pdf/26/ajc_v26_p011.pdf where it says that the Petersen graph has hull number 4.
Best,
Jernej
comment:3 in reply to: ↑ 2 Changed 6 years ago by
- By implementing a different algorithm and getting 4 as an answer
- By drawing the solution given by sage and seeing that it does not give the whole graph
- Arguing as follows. In the Petersen graph any pair of vertices is connected by a UNIQUE shortest path and has diameter 2. Hence 3 vertices give you a hull of size at most 3+ (3 \choose 2)*1 = 9
- By checking this paper http://ajc.maths.uq.edu.au/pdf/26/ajc_v26_p011.pdf where it says that the Petersen graph has hull number 4.
The paper you cite talks about the geodetic number, not the hull number. The computation that you do in 3 is only correct for the geodetic number. Thus I tend to think that the same reason explains 1 and 2 as well.
Nathann
comment:4 follow-up: ↓ 5 Changed 6 years ago by
Ooooh, but what is the thing with the cited paper about the geodetic number? Isnt that the same thing?
comment:5 in reply to: ↑ 4 Changed 6 years ago by
Ooooh, but what is the thing with the cited paper about the geodetic number? Isnt that the same thing?
No, as you can see the hull number of Petersen's graph is 3, while is geodetic number is 4 :-P
More seriously, in one case you take a set S, and add to it all points that are on a shortest uv-path, where u,v\in S.
In the second case, after having added those vertices you repeat the procedure again with the extended set S, then again, then again, then again, until you don't add anything new.
This second (larger) set is the convex hull of your initial set of points.
Nathann
comment:6 follow-up: ↓ 7 Changed 6 years ago by
Ooooh. So the convex hull of S is *not* the set of all vertices that lie on a shortest path between any u,v in S?
comment:7 in reply to: ↑ 6 Changed 6 years ago by
Ooooh. So the convex hull of S is *not* the set of all vertices that lie on a shortest path between any u,v in S?
Indeed, it is strictly larger than that in some cases. It is an iterated procedure.
Nathann
comment:8 Changed 6 years ago by
Ohhh I got confused by the cited paper then I thought its the same notion.
Closing this as fixed!
comment:9 Changed 6 years ago by
- Owner changed from (none) to azi
- Priority changed from critical to trivial
- Report Upstream changed from N/A to Completely fixed; Fix reported upstream
- Type changed from defect to PLEASE CHANGE
comment:10 Changed 6 years ago by
- Milestone changed from sage-6.5 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
The way to 'close' a ticket is to set its milestone to wontfix and to change its status to positive_review. THeeeeeen the release manager will close it.
Good evening,
Nathann
comment:11 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:12 Changed 6 years ago by
- Resolution set to worksforme
- Status changed from positive_review to closed
Hello !
I don't get it: I look at Petersen's graph, I look at vertices 4,7,8, and to me their convex hull is the whole graph. If you want to convince me that the answer is not correct, you have to tell me which vertex among the 10 is not in the convex hull of 4,7,8.
Actually, here is how it works for me:
4,7,8 are in the convex hull of 4,7,8
3 is the only neighbor of 4,8, so it is inside 2 is the only neighbor of 7,3, so it is inside 5 is the only neighbor of 7,8, so it is inside 9 is the only neighbor of 4,7, so it is inside 6 is the only neighbor of 7,9, so it is inside 1 is the only neighbor of 2,6, so it is inside 0 is the only neighbor of 4,1, so it is inside
As a conclusion, the hull number of Petersen's graph cannot be 4
:-P
Nathann