| Just Adventure News : |
| Home - Forum Home |
| Page 1 |
| 13 MAY 2004 at 3:58pm | |
| Deleted User | A clarification of the problem if you need it: My claim is that you can take any graph and split its vertices into two parts (for instance by coloring each of them either red or blue to indicate which edges that belongs to each part) in such a way that at least half of the edges in the graph will go between vertices in different parts (i.e. more than half of the edges will connect a red and a blue vertex for some possible coloring of the vertices). |
| 13 MAY 2004 at 7:27pm | |
ElfstoneGuild Master Posts : 5892 Joined: 4 NOV 2002 Status : Online | Many things not clear here. First of all, "vertex" doesn't seem to be used in the context you are using it right now. I find three definitions in mathematics, none of them including anything about graphs. I just call them "lines". Edges is fine, but we could simply say "dots". But let's stay with that term. I'm not sure I correctly understand what you are looking for. You want to divide the lines into two classes. But what about an odd number of edges? Is one class bigger than the other one? Or does it matter at all how big the classes are? This makes a difference later on. I can't proof anything. I'd just say this: e = number of edges l = e-1 = number of lines (doesn't matter anyway, haha) Just put each odd line from the left in one class. This way you end up with as many lines as at least half the amount of edges, both odd and even. And all but the outer two edges connect lines of different classes. Duh? Am I brilliant? It's 100% not the answer you are looking for. No proof. Btw: 2 edges means 1 line. Divide that into two classes... I guess you need to fix the definition a bit. Similar is true with 3 edges and 2 lines. You have your classes, but it's only one edge that connects the lines. For e>3 it works (I think). [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 13 MAY 2004 at 8:46pm | |
MichalNGrand Inquisitor  Posts : 7058 Joined: 14 SEP 2003 Status : Online | Originally Posted By Elfstone (13 MAY 2004 7:27pm) They're called "nodes". I forgot my sig. |
| Profile Search | |
| 13 MAY 2004 at 9:40pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | Originally Posted By MichalN (13 MAY 2004 8:45pm) Something rings a bell. Thanks. But that doesn't help us too much, did you notice that? [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 13 MAY 2004 at 10:10pm | |
MichalNGrand InquisitorPosts : 7058 Joined: 14 SEP 2003 Status : Online | Originally Posted By Elfstone (13 MAY 2004 9:40pm) Yes. I forgot my sig. |
| Profile Search | |
| 13 MAY 2004 at 10:15pm | |
| Deleted User | Ah, I see I need to clarify things. Good points! I'm using the terms "vertices" and "edges" because this is what they're called in all of my course literature involving graph theory. It is something of a standard it seems. I'll do both a strictly mathematical definition of what I mean and an intuitive explanation. That way I think you'll get it, whatever suits you the best. In any case, the problem is very simple to understand. Let's take the intuitive explanation first: Think of the graph represented simply as a drawing on a paper. The drawing contains a collection of dots. The dots are the vertices, or nodes. Whatever you like to call them. Between the dots you draw straight lines, connecting them. These are the edges in my formal definition. We're talking about the simplest kind of graph here, which is an undirected graph. What this means is just that for any edge, all we say about it is that it connects two specific vertices. A graph like this represents a simple pair-wise relation within a set of elements. For instance, consider a group of people. Draw them as dots on a paper, each dot representing one person. Then, for any pair of persons that considers themselves friends, draw a line between them. The lines represents friend relations, so the graph illustrates who is friends with who in the whole group. This could be useful, for instance if you wanted to see if everyone can find a friend of a friend. There's really nothing more to it. That's how you should think of the graph. Now, the claim I made before was that for any such graph, you can always split the dots into two sets, such that at least half of the lines will be connections that goes between the two sets, as opposed to between some dots within one of the sets. For instance, you could always send some of the people in a group with friend relations (assume they all live in the same country) to another country, such that half or more than the friend relations will be between people in different countries. Suppose everyone wants to call all their friends once a day on the phone. I claim that there always exists a way to send people abroad so that half of the calls will be international calls. This example can be related directly to a graph the way I describe it, so it's just the same claim in an example form. Now the formal approach. Don't let it confuse you if you already got the idea. This is just a formal explanation of the same thing, in case that's your cup of tea. In this light, you can view a graph as the true mathematical entity it really is, not constrained to (and confused with) drawings on a paper or examples using real-life applications: A simple, undirected graph G is defined as an ordered pair G=(V, E) where V is a set of vertices {v1, v2, ...} and E is a set of edges {e1, e2, ...} An edge e=(vi, vj) in E represents a connection between two vertices vi and vj in V. In a simple graph, all vertices v and edges e are unique, i.e. there exists no equivalent vertices or edges (just like the set notation suggests). The claim is that for any such graph, you can always partition the set of vertices V into two disjunct subsets A and B such that for more than half of the edges in E, we have that e=(v1, v2), where v1 belongs to A and v2 belongs to B, or vice versa. Now see if you can find a convincing argument that my suggestion is valid. Remember, the graph can look any way the definition allows, i.e. there is no limit to how many dots you draw (as long as the number is finite) and you can connect them in any way you want with lines, as long as there are dots left to connect (The maximum is the graph with lines connecting every dot to every other dot; a very messy picture if the number is high.) It doesn't matter what graph you draw though, the claim holds for all such graphs. |
| 13 MAY 2004 at 10:32pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | Ah, much clearer now, thanks! That's more than I asked for actually. This is what particularly confused me (a typo): Originally Posted By Petter_Holmberg (13 MAY 2004 3:52pm) I interpreted it the other way around. And I falsely assumed that you are talking about a graph of a function although you are clearly refering to diagrams of relations. However, my brain is in economy mode right now. Maybe later. We owe it to you after THAT explanation. [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 13 MAY 2004 at 10:43pm | |
| Deleted User | What can I say? Except... oops! [smiley=blush.gif] |
| 13 MAY 2004 at 10:44pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | Originally Posted By Petter_Holmberg (13 MAY 2004 10:43pm) There's nothing more to say now, hehe. [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 13 MAY 2004 at 10:49pm | |
| Deleted User | And don't mind me spending time on making definitions. Expressing yourself clearly and non-ambiguously is always a good exercise when it comes to mathematics. It's an important skill to acquire... This is especially true when you're trying to convince someone by doing a proof btw... [smiley=skull_laugh.gif] Don't you just love all the new smilies? |
| 13 MAY 2004 at 10:59pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | Originally Posted By Petter_Holmberg (13 MAY 2004 10:48pm) Right now, I can fully agree with this. I'm in the thick of it.
I often have to convince myself first.
[smiley=love.gif] [smiley=slurp.gif] [smiley=smile_blush.gif] Yes! [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 16 MAY 2004 at 12:14pm | |
| Deleted User | Should I reveal the answer yet? |
| 16 MAY 2004 at 2:29pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | I am currently reading a book about informatics and guess what I found... A whole chapter about graphs and what you can do with them. Your problem wasn't in there, though. :-/ But now I know that you are correct in saying vertices and edges. I can't think of anything. [smiley=sorry.gif] [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 16 MAY 2004 at 3:50pm | |
| Deleted User | Right, here it comes... For every edge {u, v}, define a random indicator variable Xuv as 0 iff the edge is connecting vertices in one of the two classes and 1 iff the edge is connecting vertices in different classes. Then flip a coin for every vertex in the graph. Let's say heads indicates that the vertex should belong in the class A and tails indicates that the vertex should belong in the class B. Now, what is the expected value of Xuv? Well, there are four possibilities: 1: Heads was flipped for both u and v, so the edge connects two vertices within the class A. Hence, Xuv=0. 2: Heads was flipped for u and tails for v, so the edge connects two vertices in different classes. Hence, Xuv=1. 3: Tails was flipped for u and heads for v, so the edge connects two vertices in different classes. Hence, Xuv=1. 4: Tails was flipped for both u and v, so the edge connects two vertices within the class B. Hence, Xuv=0. The expected value for Xuv is clearly 1/2 (the average of the four possible values). This is intuitively logical, because the coin flips will result in a roughly equal split between the vertices. But what is the expected number of edges between the classes? Well, by the linearity of expectations, we know that the expectation of the sum of the indicator variables is equal to the sum of the expectation of each indicator variable. Every indicator variable Xuv has an expectation of 1/2 and if there are e edges, there are e indicator variables as well. So the sum will be e/2. In other words, the expected number of edges connecting vertices from different classes is half of the edges in the whole graph. And here comes the beauty part: Now we know that a random, roughly equal split of the vertices in two classes is expected to result in half of the edges connecting vertices in different classes. And because this number represents an average equal split among all possible such splits, clearly all possible splits cannot result in an edge count less than this! Whenever there is one split with a lower edge count, there must be some other split(s) with a higher count to compensate for the average we've calculated. Thus, we can conclude that at least e/2 edges must connect vertices from different classes in some split, which is exactly what the original claim was! Interesting proof, isn't it? Probability theory can be a powerful tool if you know how to use it. I wasn't good enough to come up with this proof myself, but in hindsight it looks remarkably simple. |
| 16 MAY 2004 at 8:57pm | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | It looks so simple in fact, that I can't even believe it's true! I have my problems accepting that in my brain...we flip coins and that will be enough to prove it? Uhm. Hmm. No. I can't really think about this. I don't get it, I'm afraid! :-/ It's obvious that it should work, because we can choose the size of those classes as we please. So we just color those spots with lots of edges alternatingly, leaving those with not so many edges in the same class. Doesn't hurt. If the edges are quite evenly distributed, it's no problem at all. We can just make an equal divide. So, yeah, it's obvious. But to prove it...I still don't get how probability is the exact proof for this. [smiley=sorry.gif] I should worry about my own problems. Still haven't even started with my work for tomorrow... [smiley=eww.gif] That would be logic. Proving stuff in boolean algebra. [smiley=shudder.gif] (Yeah, I finally used it!) Btw, from that book I'm reading I learned that random factors in algorithms can lead to a solution much faster than anything else. Very interesting read. Edit: Thinking about it...going by my method it just means that a rise in probability in one zone (many edges, different classes) means a decrease in the other zones (few edges, same classes). Equally distributed it's an equal divide. So well, yeah...it's pretty much all probability. I still have a hard time to accept it as proof, but it seems logical to me. [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 16 MAY 2004 at 11:06pm | |
| Deleted User | Your reaction reminds me of my own! It seems so simple that it's hard to believe. I'd call it an example of beauty in mathematics. Probabilities aren't always ensuring because they really are about randomness, which we think of as something useless in ordered reasoning, but in these situations randomness comes in handy. The proof I presented is apparently solid, although I cannot quite understand it in depth. But trying to go the "ordered" way and constructing graph partitions with some sort of algorithm to prove the claim just got me into trouble. As for random factors in algorithms leading to faster answers, that is indeed an interesting topic. I'm just beginning to touch it myself. Quicksort is a well-known example. It is usually a great algorithm, but in the worst possible case it always performs terribly bad. The problem is to choose a pivot element to split up the set you're sorting in a good way. Interestingly, if you use randomness to choose such an element, it turns out to perform very well in general, as there is never a system for the worst possible case to appear all the time. Much like in the graph problem, randomness solves a difficult problem with elegance. Currently, I'm studying the class of NP-complete problems. They are very interesting, because they are subject to research with fundamental questions still unanswered. These are problems where no practically useful algorithm is known, but no one has managed to prove either the theoretical existance of such algorithms or the absence of one. Interestingly, it seems that all problems of that nature are also related to each other to the extent that if one such algorithm could be found, it could solve all problems with small modifications. Perhaps the most famous such problem is the one of finding a Hamiltonian path: Think of an arbitrary graph, like before, and try to find a path along the edges, such that each vertex is visited exactly once. This is also known as the travelling salesman problem (A salesman travels between a number of cities and wants to choose a route that takes him through all cities once, at the cheapest possible travelling cost). No one has ever succeeded to come up with a clever solution to that problem. If you do, I strongly suggest you go to the website below, submit your solution and claim your price: One million dollars! http://www.claymath.org/millennium/ |
| 17 MAY 2004 at 12:06am | |
ElfstoneGuild MasterPosts : 5892 Joined: 4 NOV 2002 Status : Online | Petter, I read about all of this just yesterday! Hamiltonian path, traveling salesman, Steiner-trees, planar graphs...all that! All but the latter are NP-complete algorithms. I think I can also mean, there is an algorithm, but noone knows whether or not it solves the problem every time and especially it's unknown if it might be the fastest possible. In case you never heard of it... Example for a Steiner-tree: There's a real word example for this. I try to keep it short. The American phone company AT&T installed a private phone network for firms in several spots. The cost of a call was calculated by the minimum distance needed to connect those installations. One day a client complained that he was in a disadvantage because of this system. There was a lot of discussion afterwards and some people finally had the plan to open up new small firms for one simple reason: to keep the conection cost down by providing a shorter way between the different spots. There's a quite famous problem related to this: Imagine 4 dots are arranged like the corners of a square. Now connect them with lines so that every dot is reachable from all the other one. Ok, that's silly. Just draw a square with one edge less. That's not very short. Draw lines from as diagonals in a square. Well, 2 crossing lines. We define that this is not allowed, now what. The solution is to place a new dot in the centre. Now you can draw a line to that from all the other 4 dots. Nice. But it still isn't the best solution. That would be to place another dot beside the previous one, connect them with a short line and center them afterwards. The first dot created a total length of 2*-/2 (if unit length = 1...-/ is a square root btw). The second dot improves it to 1+-/3, that's shorter. This was discovered by Jacob Steiner. Now AT&T had a problem. Everyone could just open some small shacks with a phone connection and reduce the costs in that way. They could do nothing about it. Until two smart people called Frank Hwang and Ding-Zhu Du in 1990 discovered that this method can save up to 13.4 per cent of length, and that's it. AT&T could start to breathe again. This problem is NP-complete. There is no algorithm to decide where to place the dots. You might imagine that people planted a lot of useless shacks back then! [smiley=laughing.gif] Example for a planar graph: There's another famous problem (I guess everyone has seen that once in his life somewhere) which requires to connect 3 houses to gas, water and electricity outlets. On a 2d-plane. No crossings allowed. Try as you might it's not possible. This is one example of a non-planar graph for exactly the reasons that make it impossible to draw it. In fact, there happens to be a guy with the name Kazimierz Kuratowski who discovered that a graph is not planar iff he includes one of two (!) partial graphs. One of which happens to look like the one in the above problem. Imagine that...only two! One looks like a domino, the other like a pentagram. Just one of those...no planar graph! That was much. I must get to work. Ohoh. Time is running. [b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&&all-time) 24, Stargate SG1, X-Files, Lost, House |
| Profile Search | |
| 18 MAY 2004 at 3:55pm | |
| Deleted User | Interesting! I wonder if the solution to the P=NP? problem will be found in the near future. It would be very exciting. The coolest thing would be if someone found a polynomial solution to one of the NP-complete problems, because that would immediately solve all the others (every such problem formulated has been proven reducable to another in polynomial time, so they are all seemingly the same problem, with only different formulations). But since so many problems are known and no one has found the solution for a single one, few people bother to try anymore. It is generally believed that these problems are not possible to solve in a feasible way, and people resort to rough approximations instead. One interesting NP-complete problem is that of packing items of different size into a limited compartment. I'm sure everyone has experienced this in real life (e.g. by trying to pack as many books as possible into a cardboard box when moving, or filling the trunk of a car before going on vacation). There really appears to be no simple, smart way of getting the optimal usage of the space. And indeed, the only known way is to text all possible packings, which is clearly infeasible for anything more than a small number of items. There is something of an art to the whole thing, and I found it pretty cool to discover why this is so from a mathematical standpoint. |
| Page 1 |
Back to Top | Home | News | Articles | Forum | About Us | Contact Us
Copyright ©2013, Just Adventure LLC. All rights reserved in the United States and throughout the world.
All other products and copyrights mentioned on
Just Adventure LLC are the property of their respective companies, and Just Adventure LLC makes no claim thereto.
Terms of Use | Privacy Policy
