Graph orientation- combinatorics?

[SMA_01]

Homework Statement

I have a graph, with 4 vertices and 4 edges, i.e. a square. I need to find all non-isomorphic orientations of this graph.

Homework Equations

"Orientation of a graph arises by replacing each edge {x,y} by one of the arcs (x,y) or (y,x)."

The Attempt at a Solution

I need help understanding this, I'm not sure how to tell if they are not isomorphic. I know what isomorphic is, but in this case it's just a square, are squares with different directions non isomorphic? So I just change the directions of the arcs? (Note: arc means edge) Any help is appreciated. Thanks.

 

[mighty2000]

Thank you for your question. I can help you understand the concept of non-isomorphic orientations of a graph. Isomorphism in this context means that two graphs have the same structure, meaning the same number of vertices and edges, and the same connections between them. In the case of orientations, it also means that the direction of the edges is the same in both graphs.

In your case, you have a square with 4 vertices and 4 edges. To find all non-isomorphic orientations, you can start by labeling the vertices and edges. For example, you can label the vertices as A, B, C, and D, and the edges as AB, BC, CD, and DA. Now, to find the non-isomorphic orientations, you can change the direction of each edge in different ways.

For example, you can have an orientation where AB is directed from A to B, BC is directed from B to C, CD is directed from C to D, and DA is directed from D to A. This is one possible orientation. Another orientation could be where AB is directed from B to A, BC is directed from C to B, CD is directed from D to C, and DA is directed from A to D. This is a different orientation, but it is still isomorphic to the first one because the structure and direction of the edges are the same.

To find all non-isomorphic orientations, you need to continue changing the direction of the edges in different ways. However, you need to make sure that you are not just rotating or reflecting the same orientation to create a different one. For example, if you have an orientation where AB is directed from A to B, and you rotate it 90 degrees clockwise, you will get an orientation where AB is directed from B to A. This is the same orientation, just rotated, so it is not considered non-isomorphic.

In summary, to find all non-isomorphic orientations of a square with 4 vertices and 4 edges, you need to label the vertices and edges, and then change the direction of each edge in different ways, making sure not to just rotate or reflect the same orientation. I hope this helps. Good luck with your homework!