Diameter of graph-usual chessboard

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Diameter
In summary: 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.
  • #1
evinda
Gold Member
MHB
3,836
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
  • #2
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?
 
  • #3
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)
 
  • #4
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)
 
  • #5
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)
 
  • #6
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)
 

FAQ: Diameter of graph-usual chessboard

What is the diameter of a usual chessboard graph?

The diameter of a usual chessboard graph is 6, meaning that the shortest path between any two squares on the chessboard is no more than 6 moves.

How is the diameter of a chessboard graph calculated?

The diameter of a chessboard graph is calculated by finding the longest path between any two squares on the chessboard. This can be determined by using algorithms such as Breadth-First Search or Dijkstra's Algorithm.

Does the diameter of a chessboard graph change for different sizes of chessboards?

Yes, the diameter of a chessboard graph will change for different sizes of chessboards. For example, a smaller 4x4 chessboard will have a diameter of 4, while a larger 10x10 chessboard will have a diameter of 10.

What is the relationship between the diameter of a chessboard graph and its edges?

The diameter of a chessboard graph is directly related to the number of edges on the chessboard. As the number of edges increases, the diameter will also increase. This is because more edges create more possible paths between squares, making it easier to reach any given square on the chessboard.

Can the diameter of a chessboard graph be reduced by adding more edges?

Yes, the diameter of a chessboard graph can be reduced by adding more edges. This is because adding more edges creates more direct paths between squares, making it easier to reach any given square on the chessboard. However, there is a limit to how much the diameter can be reduced, as eventually all squares will have a direct path between them.

Similar threads

Replies
4
Views
1K
Replies
22
Views
1K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
13
Views
493
Replies
4
Views
2K
Back
Top