anonymous
  • anonymous
Draw all the non-isomorphic, simple graphs with 3 nodes.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
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.
anonymous
  • anonymous
@freckles @satellite73
freckles
  • freckles
have you drawn any graphs yet?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
no not yet. i am trying to figure out the checks for isomorphism
freckles
  • freckles
well |dw:1449718541664:dw|
freckles
  • freckles
so you wouldn't draw all 3 of those, just one of them
freckles
  • freckles
and then there is a few more graphs you can draw
anonymous
  • anonymous
Okay, that's relatively straight forward.
anonymous
  • anonymous
There are only 2 more that i can see
freckles
  • freckles
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|
freckles
  • freckles
like A and B share and edge and C is isolated in all 3
freckles
  • freckles
anyways... let me see do you have the one with no edges?
anonymous
  • anonymous
|dw:1449718798958:dw|
freckles
  • freckles
one with: no edges one edge two edges all edges
anonymous
  • anonymous
are these isomorphic?
freckles
  • freckles
all being 3 here because that is the most we can have
freckles
  • freckles
there should be 4 graphs is what I'm saying
anonymous
  • anonymous
okay, so the number of graphs will equal the number of nodes +1
freckles
  • freckles
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
freckles
  • freckles
so I think for 4 nodes we would have 1+1+2+1+1
freckles
  • freckles
let me confirm
freckles
  • freckles
yep that seems right
freckles
  • freckles
3 nodes we have 4 graphs 4 nodes we have 6 graphs
anonymous
  • anonymous
|dw:1449719037693:dw|
anonymous
  • anonymous
is this right for 3 nodes?
anonymous
  • anonymous
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?!
freckles
  • freckles
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
freckles
  • freckles
oh wow I did miss some on the 4 nodes one I forgot about crossing over
anonymous
  • anonymous
i will draw what i have for 4 nodes as of now
freckles
  • freckles
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
anonymous
  • anonymous
|dw:1449719457179:dw|
freckles
  • freckles
we have 2 graphs consisting|dw:1449719515027:dw| of two edges... for 4 nodes: reason:
freckles
  • freckles
there is no way we can label these so that we have the same exact graph
freckles
  • freckles
so these are not isomorphic to each other
freckles
  • freckles
oops there is more with 3 edges
anonymous
  • anonymous
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?
freckles
  • freckles
|dw:1449719718327:dw|
anonymous
  • anonymous
yeah i just found those :D
freckles
  • freckles
|dw:1449719843380:dw|
freckles
  • freckles
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
freckles
  • freckles
that sum has an interesting symmetry like the 1+1+2+3+2+1+1 thing I'm talking about
anonymous
  • anonymous
yeah, that is pretty cool
freckles
  • freckles
the one with 3 though wasn't very symmetrical we had 1+1+2+1
anonymous
  • anonymous
i doubt i'll get more than 4 on my final. my study guide just asked for 3 nodes.
anonymous
  • anonymous
5 would probably blow up pretty big.
freckles
  • freckles
I don't know if there is a known formula
anonymous
  • anonymous
|dw:1449720171359:dw|
anonymous
  • anonymous
another for 3 nodes?
freckles
  • freckles
http://www.wolframalpha.com/input/?i=how+many+non-isomorphic+graphs+with+3+nodes look at this
freckles
  • freckles
that is the same as the one you had earlier
freckles
  • freckles
|dw:1449720242170:dw|
freckles
  • freckles
wolfram has for 3 nodes: 4 graphs 4 nodes: 11 graphs 5 nodes: 34 graphs 6 nodes: 156 graphs
anonymous
  • anonymous
yeah, i think hes not going to ask for more than 4 nodes hahaha
freckles
  • freckles
yep just wondering if there is a pattern for 1,2,4,11,34,156,....
anonymous
  • anonymous
i would assume so
anonymous
  • anonymous
but then again i kind of suck at math :X
freckles
  • freckles
http://math.stackexchange.com/questions/353053/is-there-a-formula-for-finding-the-number-of-nonisomorphic-simple-graphs-that-ha
freckles
  • freckles
brb
freckles
  • freckles
back
freckles
  • freckles
so yep it looks there isn't an exact formula
anonymous
  • anonymous
|dw:1449720821840:dw|
anonymous
  • anonymous
okay so here is a binary tree
anonymous
  • anonymous
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?!
anonymous
  • anonymous
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?
freckles
  • freckles
@ganeshie8 I'm not sure about what's going on here @Alexadb I might have to look this section up
anonymous
  • anonymous
ok i am looking through stuff, too. no worries :)
anonymous
  • anonymous
well, i figured out the depth is basically the same as the height.
freckles
  • freckles
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html lol so far all I understand is the levelorder
freckles
  • freckles
and I guess that tree isn't the one you gave it is the preorder graph
freckles
  • freckles
|dw:1449723559200:dw| I tried to look at the most left entries first and then move to its parent if I could
freckles
  • freckles
oh there is no 5 in that graph
freckles
  • freckles
oh you are drawing the preorder
freckles
  • freckles
I give I totally don't know

Looking for something else?

Not the answer you are looking for? Search for more explanations.