Explore tens of thousands of sets crafted by our community.
Graph Isomorphism
8
Flashcards
0/8
Node Correspondence
Two graphs are isomorphic if there is a one-to-one correspondence between their nodes that preserves edges.
Edge Preservation
Isomorphic graphs must have edges preserved exactly under the mapping of nodes.
Number of Nodes and Edges
Two graphs must have the same number of nodes (vertices) and edges to be isomorphic.
Degree Sequence
Graphs must have the same degree sequence to be isomorphic.
Subgraph Isomorphism
The presence of similar subgraphs can be indicative of isomorphism, but does not prove it on its own.
Planarity
Both graphs must be planar or both non-planar for them to be isomorphic.
Graph Automorphisms
An isomorphism of a graph onto itself is called an automorphism. The number of automorphisms can give insights into possible isomorphisms between two graphs.
Cycle Structure
Graphs should exhibit the same cycle structure to be isomorphic, including the length and number of cycles.
© Hypatia.Tech. 2024 All rights reserved.
