graph isomorphism

图的同构

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Translation evidence: Literature usage

Meaning in context

An isomorphism of simple graphs G=(V,E) and H=(W,F) is a bijection f:V→W such that uv is in E if and only if f(u)f(v) is in F for each distinct u,v.

简单图 G、H 的同构是顶点间的双射，且两点在 G 中相邻当且仅当对应两点在 H 中相邻。

Example

Relabeling the path a−b−ca-b-c as 3−1−23-1-2 gives an isomorphic graph.

Usage and distinctions

A one-way adjacency-preserving map is not enough; both adjacency and nonadjacency must be preserved by the bijection.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Keller and Trotter — Applied Combinatorics (2016)Section 5.1, graph isomorphism definition · Checked 2026-10-14

Translation sources

  1. 新疆大学 — 本科课程教学大纲汇编，图论（050762）PDF pp.94–95 / printed pp.93–94，图论课程，第一部分教学目的和要求「图的同构」 · Checked 2026-10-14
Edit source / propose a PRReport a correction

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.