| Line 16: | Line 16: | ||
• A <math>\ \text{Graph } G </math> is a pair of sets <math>\ G = (E_{G}, V_{G}) </math> , where <math>\ V_{G} </math> is the set of vertices (or "dots") in the graph and <math>\ E_{G} </math> is the set of edges (or "lines") for the graph. | • A <math>\ \text{Graph } G </math> is a pair of sets <math>\ G = (E_{G}, V_{G}) </math> , where <math>\ V_{G} </math> is the set of vertices (or "dots") in the graph and <math>\ E_{G} </math> is the set of edges (or "lines") for the graph. | ||
| − | • A <math>\ \text{Graph Isomorphism } f </math> between two graphs <math>\ G \text{ and } H </math> is a bijective function <math>\ f : V_{G} \rightarrow V_{H} </math> with the property that there is an edge between <math>\ v_{i} \text{ , } v_{j} \in V_{G} </math> if and only if there is an edge between <math>\ f(v_{i}) \text{ , } f(v_{j}) \in V_{H} </math> . In other words, this is a one-one correspondence between <math>\ G \text{ and } H </math> showing that they are in fact the same graph. One example of a | + | • A <math>\ \text{Graph Isomorphism } f </math> between two graphs <math>\ G \text{ and } H </math> is a bijective function <math>\ f : V_{G} \rightarrow V_{H} </math> with the property that there is an edge between <math>\ v_{i} \text{ , } v_{j} \in V_{G} </math> if and only if there is an edge between <math>\ f(v_{i}) \text{ , } f(v_{j}) \in V_{H} </math> . In other words, this is a one-one correspondence between <math>\ G \text{ and } H </math> showing that they are in fact the same graph. |
| + | |||
| + | One example of a graph isomorphism is the following: | ||
Revision as of 12:35, 24 April 2016
Group A: The Graph Isomorphism Problem
The Graph Isomorphism Problem
Introduction
The graph isomorphism problem has been a long-standing problem in complexity theory for the last four decades. The statement of the problem is fairly simple: Given any two finite graphs that may appear to be different, is there an "easy" way to tell whether or not the two graphs are the same? We'll look at the statement of the problem in a slightly more rigorous setting, discuss the importance of the problem in other fields, as well as some recent progress made on the problem by a professor at the University of Chicago.
Basic concepts
We'll start off with some basic concepts related to the problem and formulate a more rigorous statement of the problem.
$ \ \text{Definitions} $
• A $ \ \text{Graph } G $ is a pair of sets $ \ G = (E_{G}, V_{G}) $ , where $ \ V_{G} $ is the set of vertices (or "dots") in the graph and $ \ E_{G} $ is the set of edges (or "lines") for the graph.
• A $ \ \text{Graph Isomorphism } f $ between two graphs $ \ G \text{ and } H $ is a bijective function $ \ f : V_{G} \rightarrow V_{H} $ with the property that there is an edge between $ \ v_{i} \text{ , } v_{j} \in V_{G} $ if and only if there is an edge between $ \ f(v_{i}) \text{ , } f(v_{j}) \in V_{H} $ . In other words, this is a one-one correspondence between $ \ G \text{ and } H $ showing that they are in fact the same graph.
One example of a graph isomorphism is the following:
Importance
Recent developments
Closing Remarks
