#What is isomorphism in graphs theory and how to determine it
unborn ore
brazen sunBOT
<@&987246746478460948> please have a look, thanks.
spice scroll
in a nutshell: suppose u would rename some of the nodes and suddenly the other graph comes out
i. e. both graphs are identical if u allow node swapping/renaming
thats also called a transformation
in ur picture, the nodes top left and top right need to be swapped. then u get the other graph
spice scroll
like if we map top left to top right
two graphs are isomorphic if they are identical while allowing renaming
i. e. if u can reach one graph from the other just by remapping some nodes, they are isomorphic
unkempt whale
like if we map top left to top right
You can only move the vertices arounds or rename vertices, that's all. You can't remap edges, you can't delete or add anything
Those two are isomrphic for example : if you take the left one, and move bto the right, slighty down left, move h up, i bottom left, d bottom right, you get the right one
unborn ore
oh so my graphs arenot isomorphic
spice scroll
see, u have to understand that the way we visually represent a graph by drawing is nothing mathematical. the picture is not part of a graph.
the graph itself just consists of a list of nodes and edges connected them.
Whether u draw the graph like that G graph or like the H graph is up to us humans.
its the exact same graph, just drawn differently. from a different angle or perspective
if u take two graphs and get rid of their graphical representation and just look at their list of nodes and edges connected them, if those two look identical (i.e. ignoring the names u, as human, gave the nodes and edges), then they are isomorphic. as they are essentially the same graphs
alas pic demonstrates that very well. two graphs are isomorphic if there is an isomorphism between both. an isomorphism is a function that maps each node from the left graph to a node from the right graph in a way that both graphs still work
(i.e. "renaming")