Home
Graph repository
- Details
- Written by Jesus F. Espinoza
- Category: Research
- Hits: 133
A complete list of acyclic graphs up to 11 vertices is available here, i.e., those graphs such that the simplicial homology of its clique complex is trivial. Also, the list of connected graphs up to 11 vertices can be downloaded from here.
A numerical approach for the filtered generalized Cech complex
- Details
- Written by Jesus F. Espinoza
- Category: Research
- Hits: 376
In this page you can download the source file Cech.scale.cpp
(first version), complementary to the paper A numerical approach for the filtered generalized Cech complex. The script is also available in https://github.com/gcs-unison/Cech-scale.
The paper is available online in arXiv.
Small simple connected graphs
- Details
- Written by Héctor Hernández
- Category: Research
- Hits: 301
On this page you can find a repository of programs written in C/C++ as well as compressed data that generates these programs.
The source programs in C/C++ are written in standard C, without using additional data structure, with a understandable style.
The main idea is can compile and run programs using a standar personal computer.
- Connected graphs. The script
Cnt_Graphs_1_9.cpp
generate connected graphs of 1, 2, ..., 9 vertices. The files generated areCG_num.zip
each num represents a graph, that can changed in a adjacency matrix throughtCh_num_to_AM_1_9.cpp
with outputCG_AM.zip
. AlsoCh_num_to_CF_AM_1_9.cpp
change each num to the canonical form of the adjacency matrix. Here are the first 400 geometrical representations of connected graphs inggb
(Geogebra). - The script
CanonicalForm.cpp
takes a graph from the filegraph.txt
and return its canonical form. BothCnt_Graphs_1_9.cpp
andCanonicalForm.cpp
are using a fast technique called Canonical Labeling, written exclusively to solve the problem of isomorphism of small graphs. - Contractible graphs. Is an interesting family of graphs, because its characteristics in the homology calculation. The script
G_I.cpp
calculate ifgraph.txt
belongs or not to this family. There is another family called collapsible graphics. The scriptG_coll.cpp
performs the corresponding work. - Also
CG_to_G_Ivach_Coll_AM.cpp
takes each graph fromCG_num.zip
and filter which are contractible, in the Ivashchenko sense; at the same time verify the conjecture that they are also collapsible graphs. The ouput are files with adjacency matrix. WhileCG_to_G_Ivach_n_G_coll.cpp
show the number of graphs. - A graph belong to the contractible graphs family if can be reduced to K(1) using contractible transformations, in particular deleting vertices. A many graph dont belong to this family, but can be reduced throught this operations. This helps to reduce graphs and facilities homology calculation. See other main link.
Many graphs are not in the family contractible graphs; however, it is desirable to determine how far it is possible to eliminate vertices from the graph. The script Ivach.Red.cpp
uses the algorithm contractible.graph
to eliminate vertices when possible. The following two videos represent a filtration of graphs (actually we can think as the Vietoris-Rips filtration) and the sequence of reduced graphs, with the same persistent homology groups: