Graph theory

[exfret]

So, I'm getting really interested in graph theory for some reason. Any suggestions on what to do to learn? So far, I've been able to find a few good resources, but they've either been too technical, or just the basics. Books are actually poor to learn comprehensively from anyways, so I was almost hoping yous (I love how that actually makes grammatical sense) would know some graph theory that we could talk about, but yous probably don't even know what it is (no, it has nothing to do with f(x)=...). Oh, and I made this really cool picture of this one graph, but the file size is too big and I can't change its format because it's on my phone. It's what I call the self-reproducing graph, because to draw each new iteration, you build a connection to a new point for each existing point. I can't seem to find its real name, though. I'm sure it's been studied before, and so it has to have a name. Does anyone know what it's real/official name is?

[A Random Player]

http://www.math.utah.edu/mathcircle/not ... Theory.pdf <<Read this, try the exercises.
http://en.wikipedia.org/wiki/Glossary_of_graph_theory

Graph theory is basically connect the dots, and then analyzing how the dots are connected or counting ways to connect the dots.

Your self-reproducing graph appears to be a complete graph - There are connections between all points, and when you add a new point you connect all old points to it. Example:

[exfret]

http://www.math.utah.edu/mathcircle/not ... Theory.pdf <<Read this, try the exercises.
http://en.wikipedia.org/wiki/Glossary_of_graph_theory

These look like good sources. Thanks! May I ask if you yourself know anything about graph theory?

Your self-reproducing graph appears to be a complete graph - There are connections between all points, and when you add a new point you connect all old points to.

I was thinking I might have been a little ambiguous in what I was saying. No, it isn't an n-complete graph, but rather, a tree, which has the least possible number of connections per point for it to be still connected, which makes it the opposite of a complete graph, which has the most possible connections per point. In fact, I find complete graphs quite dull and hard to draw. In my graph, you attach to each existing point a new point. Another way to draw it after the nth iteration would be to start with a point connected to n other points, and one of those points is connected to n-1 points, the next to n-2 points, etc., and then you go on to each branch's subpoints (e.g. The n-1 main branch would have a n-2 sub-branch, a n-3, etc.) until you're left with just '0' branches. The total number of points should be 2^n, and the number of points, a, that are distance d away from the main/start point after iteration n make a Pascal's triangle (e.g. nCd=a). So, after the zeroth iteration, it would be a point, after the first, a 2-complete graph, after the second, a line of length 3 in edges or 4 in points, and after the third it gets a bit hard to describe.

Also, I'd like to explain more what I'm looking to learn. Right now, I've been on the hunt for the 'perfect' graph. I would just be content with my self-reproducing graph, but it's a tree, (trees are boring because there's only one way to get from one point to another) and its exponential growth makes it a little hard to study. I'm also wondering how you would know the number of unique graphs that contain n points or n edges, and a way to prove two graphs are equivalent without drawing them or checking each way of switching points to see if it gets an equivalent set.

[A Random Player]

http://www.math.utah.edu/mathcircle/not ... Theory.pdf <<Read this, try the exercises.
http://en.wikipedia.org/wiki/Glossary_of_graph_theory

These look like good sources. Thanks! May I ask if you yourself know anything about graph theory?

Your self-reproducing graph appears to be a complete graph - There are connections between all points, and when you add a new point you connect all old points to.

I was thinking I might have been a little ambiguous in what I was saying. No, it isn't an n-complete graph, but rather, a tree, which has the least possible number of connections per point for it to be still connected, which makes it the opposite of a complete graph, which has the most possible connections per point. In fact, I find complete graphs quite dull and hard to draw. In my graph, you attach to each existing point a new point. Another way to draw it after the nth iteration would be to start with a point connected to n other points, and one of those points is connected to n-1 points, the next to n-2 points, etc., and then you go on to each branch's subpoints (e.g. The n-1 main branch would have a n-2 sub-branch, a n-3, etc.) until you're left with just '0' branches. The total number of points should be 2^n, and the number of points, a, that are distance d away from the main/start point after iteration n make a Pascal's triangle (e.g. nCd=a). So, after the zeroth iteration, it would be a point, after the first, a 2-complete graph, after the second, a line of length 3 in edges or 4 in points, and after the third it gets a bit hard to describe.

Also, I'd like to explain more what I'm looking to learn. Right now, I've been on the hunt for the 'perfect' graph. I would just be content with my self-reproducing graph, but it's a tree, (trees are boring because there's only one way to get from one point to another) and its exponential growth makes it a little hard to study. I'm also wondering how you would know the number of unique graphs that contain n points or n edges, and a way to prove two graphs are equivalent without drawing them or checking each way of switching points to see if it gets an equivalent set.

How's this for the graph? (this feels like I'm a detective)

What I saw it as

exfret graph.png (25.7 KiB) Viewed 9211 times

I tried to embed it as a planar matchstick graph, though my first edges may have caused the rest to become messy (I could have made the first 3 edges all collinear). However, another way of visualizing it is this:
Consider the graph as infinite infinite-dimensional bitstrings (like "001001101001000..."); each bitstring is a vertex. Each bitstring has an edge that removes the last 1 in the string (towards root), or changes any 0 that is after all 1s to a 1 (away from root). A truncated version of the graph only has a finite bitstring. So a list of connections of order 4 would be:

Code: Select all

Ordered by distance from root, initial number is # of edges
4: 0000 -> 1000, 0100, 0010, 0001 (root)
4: 1000 -> 1100, 1010, 1001 (from 0000)
3: 0100 -> 0110, 0101 (from 0000)
2: 0010 -> 0011 (from 0000)
1: 0001 -> ∅ (from 0000)
3: 1100 -> 1110, 1101 (from 1000)
2: 1010 -> 1011 (from 1000)
1: 1001 -> ∅ (from 1000)
2: 0110 -> 0111 (from 0100)
1: 0101 -> ∅ (from 0100)
1: 0011 -> ∅ (from 0010)
2: 1110 -> 1111 (from 1100)
1: 1101 -> ∅ (from 1100)
1: 1011 -> ∅ (from 1010)
1: 0111 -> ∅ (from 0110)
1: 1111 -> ∅ (max distance from root)

Code: Select all

Ordered by number of edges, initial number is # of edges
4: 0000 -> 1000, 0100, 0010, 0001 (root)
4: 1000 -> 1100, 1010, 1001 (from 0000)
3: 0100 -> 0110, 0101 (from 0000)
3: 1100 -> 1110, 1101 (from 1000)
2: 0010 -> 0011 (from 0000)
2: 1010 -> 1011 (from 1000)
2: 0110 -> 0111 (from 0100)
2: 1110 -> 1111 (from 1100)
1: 0001 -> ∅ (from 0000)
1: 1001 -> ∅ (from 1000)
1: 0101 -> ∅ (from 0100)
1: 0011 -> ∅ (from 0010)
1: 1101 -> ∅ (from 1100)
1: 1011 -> ∅ (from 1010)
1: 0111 -> ∅ (from 0110)
1: 1111 -> ∅ (max distance from root)

Alternatively, start with a point. Draw a horizontal line. Draw a vertical line from each of those. Draw a line extending in the Z direction for each of those. Same for W direction. Then in the other directions.

[exfret]

How's this for the graph? (this feels like I'm a detective)...
...Alternatively, start with a point. Draw a horizontal line. Draw a vertical line from each of those. Draw a line extending in the Z direction for each of those. Same for W direction. Then in the other directions.

Exactly! You see how amazing it is? Do you know what its name is?