Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Interesting transformations on graphs!!!

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)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

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.

View Image: graf1.JPG View Image: graf2.JPG View Image: graf3.JPG View Image: graf4.JPG View Image: graf5.JPG View Image: graf6.JPG

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

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.

View Image: graf8.JPG

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

Any thoughts and/or comments about this?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

How bout an example?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

Hi bobbym

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

hi bobbym

Can you point me to a decent graph drawer?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

hi bobbym

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

well nothing too complex.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

hi bobbym

up to 10 nodes.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

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)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

hi bobbym

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

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.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

hi bobbym

see the edited #2


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

gist?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,520

Re: Interesting transformations on graphs!!!

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 big_smile


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Online

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,242

Re: Interesting transformations on graphs!!!

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.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Board footer

Powered by FluxBB