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

You are not logged in.

#1 2011-07-05 06:11:50

dangermulan1988
Member
Registered: 2011-06-11
Posts: 18

Question about a "closed walk" in a graph

Hi,

I am wondering ...
Given the following Graph:
(see image)

A walk is just something like A, B, C, B, E

In a closed walk the "begin" vertex needs to be the same as the "end" vertex.
And we are allowed in that walk to use the vertices that we cross in out walk multiple times...
So a closed walk can be A, B, C, D, E, B, A.
Where "B" is used twice and the start/begin vertex is "A"

Now ... is it correct if I assume if this is a closed walk as well?
A, B, C, B, A

Or is this not allowed?

View Image: 150px-Traversal_example.png

Offline

#2 2011-07-05 08:03:00

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

Re: Question about a "closed walk" in a graph

hi iwan_ccie

this is a kind of question i don't encounter very much.where did you get this?

as for the question itself if the route ABCDEBA is considered closed and allowed than so should it be ABCBA.

Last edited by anonimnystefy (2011-07-05 08:03:41)


“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

Offline

#3 2011-07-05 09:01:59

dangermulan1988
Member
Registered: 2011-06-11
Posts: 18

Re: Question about a "closed walk" in a graph

Thanks for the answer ...

I am just trying to understand the different walks and rules that apply to them...

So this means that A, B, A, B, A, B, C, B, A is also a closed walk?

Thanks,

Offline

#4 2011-07-05 09:10:48

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

Re: Question about a "closed walk" in a graph

hi iwan_ccie

a closed walk is only when the first and the last letter are the same.
an allowed walk is the one that includes a vertex that is unmarked on your image.

your welcome.


“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

Offline

#5 2011-07-05 09:14:15

dangermulan1988
Member
Registered: 2011-06-11
Posts: 18

Re: Question about a "closed walk" in a graph

So it does not really matter how the walk goes in a closed walk... as long as the begin and end vertex are the same... Right?

So this means that A, B, A, B, A, B, C, B, A is also a closed walk and allowed right?

Thanks,

Last edited by iwan_ccie (2011-07-05 09:15:31)

Offline

#6 2011-07-05 09:20:21

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

Re: Question about a "closed walk" in a graph

yup.


“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

Offline

#7 2011-07-05 09:21:42

dangermulan1988
Member
Registered: 2011-06-11
Posts: 18

Re: Question about a "closed walk" in a graph

Thanks!

Offline

Board footer

Powered by FluxBB