MHB Diameter of graph-usual chessboard

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Diameter
AI Thread Summary
The diameter of the graph representing a chessboard, where vertices are the squares and edges connect adjacent squares, is not 64. The diameter is defined as the longest shortest path between any two vertices. Since moving from one edge of the board to the opposite edge requires at least 8 steps, the diameter is at least 8. Additionally, it cannot exceed 64, as there are shorter paths available. Therefore, the diameter of the chessboard graph is confirmed to be 8.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)
 
Physics news on Phys.org
evinda said:
Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)

Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?
 
I like Serena said:
Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?

Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)
 
evinda said:
Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)

Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)
 
I like Serena said:
Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)

I don't really know (Worried) Could you give me a hint?? (Blush)
 
evinda said:
I don't really know (Worried) Could you give me a hint?? (Blush)

Well... we can only go from one square to another if those squares are next to each other.
So if we start from 1 end of the board and step to the other side, we're making 8 steps. We can't do it any faster.
That means that the diameter is at least 8.

If we start from one square and take 64 steps to get to some other square, then I think we can also find a shorter path (the distance of 2 squares is the length of the shortest path).
That means that the diameter is less than 64.

Can you find 2 squares for which it will have to take more than 8 steps to cross from the one to the other? (Wondering)
 

Similar threads

Back
Top