法语入门Master’s Project Report Graph Reconstruction Numbers
Jennifer Baldwin
jlb5851@cs.rit.edu
Rochester Institute of Technology
Department of Computer Science
102Lomb Memorial Drive
Rochester,NY14623-5608 Chairman:Edith Hemaspaandra
的英文
Reader:Stanis l aw P.Radziszowski
Obrver:Darren Narayan江沪日语
July30,2004
Abstract
One of the most important open questions in graph theory is the graph reconstruction conjecture,first propod by P.J.Kelly and S.M.Ulam in1941.The conjecture states that every graph with at least3vertices is ,if there exists some multi-subt of vertex-deleted subgraphs that reconstructs G uniquely up to isomorphism.This project computes the existential and universal reconstruction numbers for all graphs of order at most eight and26,000 graphs of order nine.The existential reconstruction number is the number of vertex-deleted subgraphs,or cards,required to reconstruct G uniquely up to isomorphism.The universal reconstruction number is the minimum number of cards for which all multi-subts of that size reconstruct G uniquely up to isomorphism.
The graph reconstruction conjecture is still unproven,but the re-sults of this project help provide more information.Many theorems relating to the existential reconstruction number were verified by my results.We also refute a conjecture of Harary and Plantholt.The conjecture stated that the upper bound of the existential reconstruc-
tion number is n
2+1.We show two graphs that have an existential
reconstruction number of6when the upper bound defined conjectured by Harary and Plantholt is5.Th
e universal reconstruction number has been rearched very little so far.The reconstruction numbers produced by this project help support the opinion that most graphs are easily reconstructible.
1
Contents
1Background5 2General Project Description13 3Implementation14 4Results27 5Future Work33
2
List of Figures
1Example Graph and its Deck (5)眼花缭乱是什么意思
2Reconstruction of G (7)
3G and D(G) (9)
4Extension graphs of D(G) (9)
5Reconstruction attempt#1 (10)
6Reconstruction attempt#2 (10)
7Reconstruction attempt#3 (10)
8Reconstruction attempt#4 (11)
9Two non-isomorphic graphs with the same edge deck (12)
10Conversion from matrix to bit vector to graph6format (15)
11Adding a vertex to the bit vector reprentation (15)south是什么意思
12Removing a vertex from the bit vector reprentation (16)
13Example run of expand (17)cute什么意思
14Key of graphs in the example run of expand (17)
15Example run of shrink (18)
16Key of graphs in the example run of shrink (18)
17Example run of makeGraph (19)
18Algorithm for determining∃rn(G) (20)
19Algorithm for determining∀rn(G) (20)
20Description of preliminary steps for computing reconstruction numbers (20)
21Example run of reconstruct (21)
laydown22All graphs of order4with∃rn(G)=4 (28)
23All graphs of order6with∃rn(G)>3 (28)
24All graphs of order8with∃rn(G)>3 (29)
25All graphs of order6with∃rn(G)=∀rn(G)=5 (30)
26All graphs of order8with∀rn(G)=5or6 (30)
3
List of Tables
1∃rn(G)counts (30)
2∀rn(G)counts (31)
3Percentages of∀rn(G)as a function of n (31)
4Counts of∃rn(G)and∀rn(G)pairs (32)
5Count of reconstruction numbers within class of graphs..34 6Count of(∃rn(G),∀rn(G))Pairs for26,446out of274,668 Graphs of Order9 (35)
4
Figure1:Example Graph and its Deck
1Background
In order to understand what graph reconstruction is,one must first under-stand what a deck and a card is.Given a graph G,a card reprents the subgraph created by deleting a single vertex of G.A deck for graph G,de-noted D(G)is the multi-t containing all the vertex-deleted subgraphs of
G[3,13,8].The deck is considered a multi-t becau it is possible that
G−v i∼=G−v j,but the two subgraphs were created by removing different vertices and are therefore defined as different cards.A graph G is recon-structible if there exists some multi-subt of the deck that can be ud to create a unique graph H that is isomorphic to G.H is considered unique up
to isomorphism if all of the graphs that can be constructed from its multi-subt of cards have the same canonical labeling.A graph G is isomorphic
solemnlyto a graph H,if there exists a bijectionσ:V(G)→V(H)such that an edge uv∈E(G)⇐⇒σ(u)σ(v)∈E(H).In other words,there must exist
a function for which every edge in G corresponds to a single edge in H.A canonical labeling is a way of relabeling the vertices of G,while retaining G’s connectivity.There exist many algorithms that have
the purpo of canoni-cally labeling a graph.If two graphs have the same canonical labeling,then they are isomorphic.Each algorithm approaches the problem in a different way.Another way of determining that G is unique is via a top-down ap-proach.If no other graph of the same order as G has a multi-subt of cards equivalent to the one that creates G,then G is unique up to isomorphism. Figure1shows a graph G and its deck.Note that in this ca G is the only graph up to isomorphism with deck D(G).
The Reconstruction Conjecture(P.J.Kelly,[7],and S.M.Ulam,[14]): Every graph with at least three vertices is reconstructible[3,8,1,13].
varnish>mandrake5
