Interesting transformations on graphs!!!

anonimnystefy · 2012-03-10 09:03:44

hi guys

Not long ago i came up with an interesting algorithm that can be used to see in how many moves of a pencil a graph can be drawn.I don't know whether it's a thing in graph theory or not,but i will describe it in the next post.

I was also trying to come up with a nice way to represent binary trees,trees in general and graphs in general.I have found a representation for a general graph,but it is not well defined because there are some cases in which two graphs have the same representation.I will explain the notation in another post.

Last edited by anonimnystefy (2012-03-10 09:17:54)

anonimnystefy · 2012-03-10 09:15:28

So,we have the next transformation that can be used to find the 'drawability' of a graph:

Let's notice three points we label with 1,2 and 3,such that 1 is connected with 2 and 2 is connected with 3.The transformation allows us to erase the connections 1-2 and 2-3 and establish a connection between 1 and 3.

This transformation has some corollaries and properties:

1)The transformation keeps the 'drawability' of a graph the same.

2)From 1) we have that we can erase any loops in the graph keeping the drawability the same.

3)From the definition of the transformation and 2) we get that we can delete any two paths that connect the same two pots.E.g. if we have nodes 1 and 2 connected twice we can erase both of those connections.

4)From the definition of the transformation and 3) we get that we can erase any closed cycle in the graph.E.g. if nodes 1,2,3,4 and 5 have the connections {(1,2);(2,3);(3,4);(4,5);(5,1)} among them than we can delete all of these connections because they form a closed cycle.

5)We can define the inverse of these transformation to be the inverse of any of these definitions and corollaries.E.g. we can form a loop on any node we want,we can establish two paths between any two points,establish a cycle between any number of points and so on...

EDIT:I have added pictures of the processes.The first one shows the 'erasing the loop' step,the second show the definition of the transformation and the other four show step-by-step process of the complete transformation on a regular K5 graph (which is the connected five node graph) which ends up with only 5 unconnected nodes,which means that it is drawable.

Some definitions using this transformation:

A graph is completely transformed if and only if the transformation given above cannot be applied anymore.

Drawability of a completely transformed graph is the same as the number of lines the graph is consisted of.If a graph has the drawability 1 then we can call it drawable.

Drawability of any graph is the same as the drawability of a graph gained by applying the transformation described above.

Last edited by anonimnystefy (2012-03-12 00:03:36)

anonimnystefy · 2012-03-10 09:23:11

The notation is:

If we number the nodes of an n-node graph arbitrarily with numbers 0,1,2,...,n-1 (but preferable so that as many nodes connected to each other have their numbers differing by 1) and then for each for each node we count the number of paths coming out of it (i.e. the degree of the node) and label it with d[sub]i[/sub] where i is the number of the node then to that graph we assign the next polynomial:

The problem with this notation is that some graphs have the same polynomials,but what this notation is good for is defining the addition and multiplication of two graphs,because that are the operations we can do with the polynomials.

Another thing we can do with this kind of notation is represent directed graphs,whilst counting the paths coming out of a node as 1 and a path coming into a node as -1.

Last edited by anonimnystefy (2012-03-12 22:13:14)

anonimnystefy · 2012-03-11 04:33:47

Any thoughts and/or comments about this?

bobbym · 2012-03-11 04:36:55

How bout an example?

anonimnystefy · 2012-03-11 04:38:55

Hi bobbym

Sure.Let me see if I can go on my laptop.

bobbym · 2012-03-11 04:42:15

Yes, always pose your stuff in the form of a problem with an example. Then examplists can sink our teeth into.

Example of an example.

I have twelve balls, they are lablled a,b,c,d,e...

11 of them or exactly the same and one is different. Find the different one in three weighings of a pan balance.

anonimnystefy · 2012-03-11 05:06:10

hi bobbym

Can you point me to a decent graph drawer?

bobbym · 2012-03-11 05:16:55

Hi anonimnystefy;

Not offhand. I downloaded a couple of them a long time ago and never got around to trying any of them. I do not even remember their names. I am sorry for that.

How detailed are the graphs?

anonimnystefy · 2012-03-11 05:19:04

hi bobbym

i meant the graph theory graphs,just to be on the same page.

well nothing too complex.

bobbym · 2012-03-11 05:19:32

That is what I meant. How many nodes and edges?

anonimnystefy · 2012-03-11 05:21:23

hi bobbym

up to 10 nodes.

bobbym · 2012-03-11 05:31:17

That is not too bad. You might try drawing it by hand with geogebra. Line segment by line segment. Or how about a simpler example?

If not then I withdraw the request and we will talk about something else.

anonimnystefy · 2012-03-11 05:33:06

hi bobbym

no,an example would be really good.let we try to draw it up in GG real fast.

Last edited by anonimnystefy (2012-03-11 05:34:19)

bobbym · 2012-03-11 06:19:05

Okay, but if it can not be done then just forget it.

anonimnystefy · 2012-03-11 06:22:18

hi bobbym

i don't know how to make it into a picture.

bobbym · 2012-03-11 06:24:29

Okay, thanks for trying. I am going to take a little break, see you later.

anonimnystefy · 2012-03-11 06:33:14

hi bobbym

ok,thanks.is there any other way to try to draw it up so that i can post it here.

see you later.

bobbym · 2012-03-11 06:50:17

You can draw it freehand on paper and scan it. Or there are many drawing programs, Inkscape, The Gimp, Irfan View and a million others.

anonimnystefy · 2012-03-11 09:02:02

hi bobbym

see the edited #2

bobbym · 2012-03-11 10:30:41

Okay, so what is the gist of your argument? In 100 words or less.

anonimnystefy · 2012-03-11 10:38:26

gist?

bobbym · 2012-03-11 10:41:03

The meat, the germ of the idea. Where you are going with this etc.

anonimnystefy · 2012-03-11 10:47:26

hi bobbym

maybe describe some hypothesis based on this transformation. i don't know,i shouldn't do all the work.i gave the transformation,someone else should do something with it

bobbym · 2012-03-11 11:04:53

Forget a new hypothesis. Forget that hypothesis kaboobly doo altogether. A hypothesis is very much like a hippopotamus. A very dangerous creature.

I need an explanation of your idea.

Math Is Fun Forum

#1 2012-03-10 09:03:44

Interesting transformations on graphs!!!

#2 2012-03-10 09:15:28

Re: Interesting transformations on graphs!!!

#3 2012-03-10 09:23:11

Re: Interesting transformations on graphs!!!

#4 2012-03-11 04:33:47

Re: Interesting transformations on graphs!!!

#5 2012-03-11 04:36:55

Re: Interesting transformations on graphs!!!

#6 2012-03-11 04:38:55

Re: Interesting transformations on graphs!!!

#7 2012-03-11 04:42:15

Re: Interesting transformations on graphs!!!

#8 2012-03-11 05:06:10

Re: Interesting transformations on graphs!!!

#9 2012-03-11 05:16:55

Re: Interesting transformations on graphs!!!

#10 2012-03-11 05:19:04

Re: Interesting transformations on graphs!!!

#11 2012-03-11 05:19:32

Re: Interesting transformations on graphs!!!

#12 2012-03-11 05:21:23

Re: Interesting transformations on graphs!!!

#13 2012-03-11 05:31:17

Re: Interesting transformations on graphs!!!

#14 2012-03-11 05:33:06

Re: Interesting transformations on graphs!!!

#15 2012-03-11 06:19:05

Re: Interesting transformations on graphs!!!

#16 2012-03-11 06:22:18

Re: Interesting transformations on graphs!!!

#17 2012-03-11 06:24:29

Re: Interesting transformations on graphs!!!

#18 2012-03-11 06:33:14

Re: Interesting transformations on graphs!!!

#19 2012-03-11 06:50:17

Re: Interesting transformations on graphs!!!

#20 2012-03-11 09:02:02

Re: Interesting transformations on graphs!!!

#21 2012-03-11 10:30:41

Re: Interesting transformations on graphs!!!

#22 2012-03-11 10:38:26

Re: Interesting transformations on graphs!!!

#23 2012-03-11 10:41:03

Re: Interesting transformations on graphs!!!

#24 2012-03-11 10:47:26

Re: Interesting transformations on graphs!!!

#25 2012-03-11 11:04:53

Re: Interesting transformations on graphs!!!

Board footer