At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I'm trying to look up how to do this; but, if anyone can quickly explain that would be great because the search is taking longer than I thought.
have you drawn any graphs yet?
no not yet. i am trying to figure out the checks for isomorphism
so you wouldn't draw all 3 of those, just one of them
and then there is a few more graphs you can draw
Okay, that's relatively straight forward.
There are only 2 more that i can see
and those are isomorphic because I can choose to label each of them in such way that they are the same graph |dw:1449718742345:dw|
like A and B share and edge and C is isolated in all 3
anyways... let me see do you have the one with no edges?
one with: no edges one edge two edges all edges
are these isomorphic?
all being 3 here because that is the most we can have
there should be 4 graphs is what I'm saying
okay, so the number of graphs will equal the number of nodes +1
well let's see... say we have 4 nodes... well no edges, there is one graph and one edge, there is 1 graph 2 edges, there is...I think 2 3 edges, there is 1 4 edges, there is 1
so I think for 4 nodes we would have 1+1+2+1+1
let me confirm
yep that seems right
3 nodes we have 4 graphs 4 nodes we have 6 graphs
is this right for 3 nodes?
is there a formula to tell how many graphs there should be? also, with 4 nodes i can see 0-4 edges; but, how does the 6th graph come in? don't we need one with 5 edges?!
oh I was confused at first I drew all of my nodes in the same position each time... yes you have the empty edge one which is the first row the one edge which is the 2nd row and third row with the 2 edge one and the last one with 3 edges
oh wow I did miss some on the 4 nodes one I forgot about crossing over
i will draw what i have for 4 nodes as of now
4 nodes: empty->1 one->1 two->2 three->1 four->1 five->1 six->1 so it should be 1+1+2+1+1+1+1 I think or 8
we have 2 graphs consisting|dw:1449719515027:dw| of two edges... for 4 nodes: reason:
there is no way we can label these so that we have the same exact graph
so these are not isomorphic to each other
oops there is more with 3 edges
okay, so direction of the edges matters too. not just edges. that makes 7 graphs, though. is there an 8th? and is there a formula to tell the number of non isomorphic graphs?
yeah i just found those :D
updating new list for 4 nodes: 4 nodes: empty->1 one->1 two->2 three->3 four->2 five->1 six->1 so it should be 1+1+2+3+2+1+1 I think or 11
that sum has an interesting symmetry like the 1+1+2+3+2+1+1 thing I'm talking about
yeah, that is pretty cool
the one with 3 though wasn't very symmetrical we had 1+1+2+1
i doubt i'll get more than 4 on my final. my study guide just asked for 3 nodes.
5 would probably blow up pretty big.
I don't know if there is a known formula
another for 3 nodes?
http://www.wolframalpha.com/input/?i=how+many+non-isomorphic+graphs+with+3+nodes look at this
that is the same as the one you had earlier
wolfram has for 3 nodes: 4 graphs 4 nodes: 11 graphs 5 nodes: 34 graphs 6 nodes: 156 graphs
yeah, i think hes not going to ask for more than 4 nodes hahaha
yep just wondering if there is a pattern for 1,2,4,11,34,156,....
i would assume so
but then again i kind of suck at math :X
so yep it looks there isn't an exact formula
okay so here is a binary tree
my next questions: a. do i have to sort the list before constructing the tree? b. where does 5 go? it could go to the right of 3 or the left of 8?!
and, does the depth of the tree = the height of the tree? meaning the root is 0 and the last leaf is dept 3? or do i start at 1 and count to the last leaf?
@ganeshie8 I'm not sure about what's going on here @Alexadb I might have to look this section up
ok i am looking through stuff, too. no worries :)
well, i figured out the depth is basically the same as the height.
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html lol so far all I understand is the levelorder
and I guess that tree isn't the one you gave it is the preorder graph
|dw:1449723559200:dw| I tried to look at the most left entries first and then move to its parent if I could
oh there is no 5 in that graph
oh you are drawing the preorder
I give I totally don't know