Determine if the graph isomorphic

Thread starter hyderman
Start date Mar 14, 2007
Tags

Graph

In summary, two graphs are isomorphic if they have the same structure, meaning they have the same number of vertices and edges and the edges are connected in the same way. There are various methods for determining graph isomorphism, such as visual comparison, mapping techniques, and algorithms. Some properties, like degree sequence and number of connected components, can also assist in quickly identifying isomorphic graphs, but they are not always reliable. Two graphs must have the same number of vertices to be isomorphic, and determining isomorphism is a difficult and unsolved problem in computer science and mathematics.

Mar 14, 2007

hyderman

hello

how can i determine if the graph isomorphic

is there is steps to do that

thanx

Physics news on Phys.org

Mar 14, 2007

HallsofIvy

Science Advisor

Homework Helper

First, tell us what the graph is!

Second, what is the definition of "isomorphism" for graphs?

Mar 14, 2007

hyderman

i have the images in this file please click and see

thanx

http://download.yousendit.com/B7955B3525D78CEB

1. What does it mean for two graphs to be isomorphic?

Two graphs are isomorphic if they have the same structure, meaning that they have the same number of vertices and edges and the edges are connected in the same way. It is like two different maps of the same city - they may look different but they still show the same streets and intersections.

2. How can we determine if two graphs are isomorphic?

There are a few methods for determining if two graphs are isomorphic. One approach is to visually compare the two graphs and see if they have the same structure. Another method is to use a mapping or relabeling technique, where you assign labels to the vertices of one graph and see if you can find a way to relabel the vertices of the other graph to match. There are also algorithms and computer programs that can assist with determining graph isomorphism.

3. Are there any properties that can help to quickly identify if two graphs are isomorphic?

Yes, there are a few properties that can be used to quickly determine if two graphs are isomorphic. One is the degree sequence, which is the list of degrees of each vertex in a graph. If two graphs have the same degree sequence, they are likely isomorphic. Another property is the number of connected components - if two graphs have a different number of connected components, they cannot be isomorphic. However, these properties are not foolproof and other methods should also be used to confirm isomorphism.

4. Can two graphs be isomorphic if they have a different number of vertices?

No, two graphs must have the same number of vertices in order to be isomorphic. This is because isomorphism is based on the structure of the graphs, and if the number of vertices is different, the structure will also be different. However, it is possible for two graphs to have the same number of vertices and not be isomorphic.

5. Is determining graph isomorphism a difficult problem?

Yes, determining if two graphs are isomorphic is a difficult problem. In fact, it is considered an unsolved problem in computer science and mathematics. While there are some known methods and algorithms for determining isomorphism, they are not always efficient or accurate. The difficulty of this problem is what makes it an interesting and challenging topic for researchers in the field.