File:Chang graphs.svg
![File:Chang graphs.svg](https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Chang_graphs.svg/400px-Chang_graphs.svg.png?20100929091508)
Исходный файл (SVG-файл, номинально 800 × 1200 пкс, размер файла: 72 КБ)
Краткие подписи
Краткие подписи
Содержание
Краткое описание
[править]ОписаниеChang graphs.svg |
English: The Chang Graphs.
The Chang Graphs are strongly regular graphs with parameters (28,12,6,4). On the right the tree Chang Graphs; these graphs are generated by selecting a proper switching set. On the left the originating [Triangular Graph]s T8: the vertices in the switching set are green, the deleted edges are red and new added ones are phantom blue. |
Дата | |
Источник | Собственная работа |
Автор | Claudio Rocchini |
Права (Повторное использование этого файла) |
CC-BY 3.0 |
References
[править]Many thanks to Nadia Hamoudi for paper "The Chang graphs" at Nadia Hamoudi "The Chang graphs" archive copy at the Wayback Machine
A note: nauty software shows an automorphism group really poor for this graphs.
Source
[править]Dirty C++ source code of graph generation and display:
/*********************************
* Drawing the Chang Graphs
* (C) 2010 Claudio Rocchini
* CC-BY 3.0
* Many thanks to Nadia Hamoudi for
* "The Chang graphs".
*********************************/
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <vector>
#include <set>
#include <algorithm>
const double PI = 3.1415926535897932384626433832795;
class point2 { public: double x,y; };
typedef std::pair<size_t,size_t> edge;
class graph {
public:
size_t nv;
std::vector<edge> edges;
int find_edge( const edge & e ) const {
std::vector<edge>::const_iterator i = std::find(edges.begin(),edges.end(),e);
return i==edges.end() ? -1 : i - edges.begin();
}
};
bool is_strong_regular( const graph & g, int & K, int & LAMDA, int & MU ) {
int i,j,k;
std::vector<bool> MA(g.nv*g.nv); std::fill(MA.begin(),MA.end(),false);
std::vector<edge>::const_iterator q;
K = -1;
for(q=g.edges.begin();q!=g.edges.end();++q) {
MA[(*q).first+g.nv*(*q).second] = true;
MA[(*q).second+g.nv*(*q).first] = true;
}
std::vector<int> adj(g.nv);
std::fill(adj.begin(),adj.end(),0);
for(k=0;k<int(g.nv*g.nv);++k) if(MA[k]) {
i = k%g.nv; j = k/g.nv;
if(i<j) { ++adj[i]; ++adj[j]; }
}
for(i=1;i<int(g.nv);++i) if(adj[0]!=adj[i])
return false;
K = adj[0];
LAMDA = -1; MU = -1;
for(i=0;i<int(g.nv)-1;++i) for(j=i+1;j<int(g.nv);++j) {
int n = 0;
for(k=0;k<int(g.nv);++k) if(k!=i && k!=j)
if( MA[i*g.nv+k] && MA[j*g.nv+k] ) ++n;
if( MA[i*g.nv+j] ) {
if(LAMDA==-1) LAMDA = n;
else if(LAMDA!=n )
return false;
} else {
if(MU==-1) MU = n;
else if(MU!=n )
return false;
}
}
return true;
}
void make_K(graph & g, size_t n, std::vector<point2> & pos) {
g.nv = n; g.edges.clear();
for(size_t i=0;i<n-1;++i)
for(size_t j=i+1;j<n;++j)
g.edges.push_back(edge(i,j));
pos.resize(n);
for(size_t k=0;k<n;++k) {
const double a = 2*PI*k/n + PI/2;
pos[k].x = cos(a);
pos[k].y = sin(a);
}
}
void make_line( const graph & g, const std::vector<point2> & ipos, graph & l, std::vector<point2> & opos ) {
l.nv = g.edges.size();
l.edges.clear();
for(size_t i=0;i<g.edges.size()-1;++i)
for(size_t j=i+1;j<g.edges.size();++j)
if(g.edges[i].first ==g.edges[j].first || g.edges[i].first ==g.edges[j].second ||
g.edges[i].second==g.edges[j].first || g.edges[i].second==g.edges[j].second )
l.edges.push_back( edge(i,j) );
opos.resize(l.nv);
for(size_t k=0;k<g.edges.size();++k) {
opos[k].x = (ipos[g.edges[k].first].x + ipos[g.edges[k].second].x)/2;
opos[k].y = (ipos[g.edges[k].first].y + ipos[g.edges[k].second].y)/2;
}
}
void invert( const graph & g, const std::set<size_t> & iset, graph & ig ) {
size_t i,j;
std::set<edge> re;
ig.nv = g.nv; ig.edges.clear();
for(i=0;i<g.edges.size();++i) {
bool inf = iset.find(g.edges[i].first )!=iset.end();
bool ins = iset.find(g.edges[i].second)!=iset.end();
if(inf ^ ins) re.insert(g.edges[i]);
else ig.edges.push_back(g.edges[i]);
}
for(i=0;i<g.nv-1;++i)
for(j=i+1;j<g.nv;++j) {
bool inf = iset.find(i)!=iset.end();
bool ins = iset.find(j)!=iset.end();
if((inf ^ ins) && re.find(edge(i,j))==re.end())
ig.edges.push_back(edge(i,j));
}
}
const double SX = 800;
const double SY = 1200;
const double RR = 7;
const double BO = 10;
void save_svg2_start( FILE * fo ) {
fprintf(fo,
"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
"<svg\n"
"xmlns:svg=\"http://www.w3.org/2000/svg\"\n"
"xmlns=\"http://www.w3.org/2000/svg\"\n"
"version=\"1.0\"\n"
"width=\"%g\"\n" "height=\"%g\"\n"
"id=\"changgraphs\">\n"
,SX,SY
);
}
void save_svg2( FILE * fo, const graph & g, const std::vector<point2> & pos, const std::set<size_t> & rset,
double ox, double oy ) {
std::vector<double> px(g.nv);
std::vector<double> py(g.nv);
int i;
const double R = ((SX/2-BO*2)/2);
for(i=0;i<int(g.nv);++i) {
px[i] = ox+SX/4 + R*pos[i].x;
py[i] = oy+SY/6 + R*pos[i].y;
}
const int ecolor[3][3] = { {0,0,0},{128,0,0},{0,0,64} };
fprintf(fo,"<g style=\"stroke:#%02X%02X%02X;stroke-width:1.5;stroke-opacity:0.2\">\n"
,ecolor[2][0],ecolor[2][1],ecolor[2][2]);
for(int a=0;a<int(g.nv)-1;++a)
for(int b=a+1;b<int(g.nv);++b)
{
bool f1 = rset.find(a)==rset.end();
bool f2 = rset.find(b)==rset.end();
if(f1==f2) continue;
if( g.find_edge( edge(a,b) )==-1 )
fprintf(fo,
"<line x1=\"%3.1lf\" y1=\"%3.1lf\" x2=\"%3.1lf\" y2=\"%3.1lf\"/>\n"
,px[a],py[a]
,px[b],py[b]
);
}
fprintf(fo,"</g>\n");
for(int mode=0;mode<2;++mode) {
fprintf(fo,"<g style=\"stroke:#%02X%02X%02X;stroke-width:1.5;stroke-opacity:0.75\">\n"
,ecolor[mode][0],ecolor[mode][1],ecolor[mode][2]);
for(i=0;i<int(g.edges.size());++i)
{
bool f1 = rset.find(g.edges[i].first)==rset.end();
bool f2 = rset.find(g.edges[i].second)==rset.end();
if( (mode==0 && f1==f2) || (mode==1 && f1!=f2) )
fprintf(fo,
"<line x1=\"%3.1lf\" y1=\"%3.1lf\" x2=\"%3.1lf\" y2=\"%3.1lf\"/>\n"
,px[g.edges[i].first ],py[g.edges[i].first ]
,px[g.edges[i].second],py[g.edges[i].second]
);
}
fprintf(fo,"</g>\n");
}
fprintf(fo,"<g id=\"nodes\" style=\"stroke:#000000;stroke-width:1;fill:#0000FF\">\n");
for(i=0;i<int(g.nv);++i) if(rset.find(i)==rset.end())
fprintf(fo,"<circle cx=\"%3.1lf\" cy=\"%3.1lf\" r=\"%g\"/>\n",px[i],py[i],RR);
fprintf(fo,"</g>\n");
fprintf(fo,"<g id=\"nodes\" style=\"stroke:#000000;stroke-width:1;fill:#00E000\">\n");
for(i=0;i<int(g.nv);++i) if(rset.find(i)!=rset.end())
fprintf(fo,"<circle cx=\"%3.1lf\" cy=\"%3.1lf\" r=\"%g\"/>\n",px[i],py[i],RR);
fprintf(fo,"</g>\n");
}
void save_svg2_end( FILE * fo ) {
fprintf(fo,"</svg>\n");
}
int main() {
size_t i;
graph K8,T8,chang1,chang2,chang3;
std::vector<point2> k8_pos,t8_pos;
std::set<size_t> empty,rset1,rset2,rset3;
make_K(K8,8,k8_pos); printf("%u %u\n",K8.nv,K8.edges.size());
make_line(K8,k8_pos,T8,t8_pos); printf("%u %u\n",T8.nv,T8.edges.size());
int K,LAMBDA,MU;
if(!is_strong_regular(T8,K,LAMBDA,MU)) printf("error");
else printf("t8: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
FILE * fo = fopen("c:\\temp\\chang_graphs.svg","w");
save_svg2_start(fo);
std::vector<edge> fourK2;
fourK2.push_back( edge(0,1) ); fourK2.push_back( edge(2,3) );
fourK2.push_back( edge(4,5) ); fourK2.push_back( edge(6,7) );
for(i=0;i<fourK2.size();++i) rset1.insert( K8.find_edge( fourK2[i] ) );
invert(T8,rset1,chang1);
if(!is_strong_regular(chang1,K,LAMBDA,MU)) printf("error");
else printf("chang1: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
save_svg2(fo,T8,t8_pos,rset1,0,0);
save_svg2(fo,chang1,t8_pos,empty,SX/2,0);
std::vector<edge> c8;
c8.push_back( edge(0,1) ); c8.push_back( edge(1,2) );
c8.push_back( edge(2,3) ); c8.push_back( edge(3,4) );
c8.push_back( edge(4,5) ); c8.push_back( edge(5,6) );
c8.push_back( edge(6,7) ); c8.push_back( edge(0,7) );
for(i=0;i<c8.size();++i) rset2.insert( K8.find_edge( c8[i] ) );
invert(T8,rset2,chang2);
if(!is_strong_regular(chang2,K,LAMBDA,MU)) printf("error");
else printf("chang2: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
save_svg2(fo,T8,t8_pos,rset2,0,SY/3);
save_svg2(fo,chang2,t8_pos,empty,SX/2,SY/3);
std::vector<edge> c3uc5;
c3uc5.push_back( edge(0,3) ); c3uc5.push_back( edge(3,5) );
c3uc5.push_back( edge(0,5) );
c3uc5.push_back( edge(1,2) ); c3uc5.push_back( edge(2,4) );
c3uc5.push_back( edge(4,6) ); c3uc5.push_back( edge(6,7) );
c3uc5.push_back( edge(1,7) );
for(i=0;i<c3uc5.size();++i) rset3.insert( K8.find_edge( c3uc5[i] ) );
invert(T8,rset3,chang3);
if(!is_strong_regular(chang3,K,LAMBDA,MU)) printf("error\n");
else printf("chang3: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
save_svg2(fo,T8,t8_pos,rset3,0,SY*2/3);
save_svg2(fo,chang3,t8_pos,empty,SX/2,SY*2/3);
save_svg2_end(fo);
fclose(fo);
return 0;
}
Лицензирование
[править]![w:ru:Creative Commons](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/CC_some_rights_reserved.svg/90px-CC_some_rights_reserved.svg.png)
![атрибуция](https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Cc-by_new_white.svg/24px-Cc-by_new_white.svg.png)
![распространение на тех же условиях](https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Cc-sa_white.svg/24px-Cc-sa_white.svg.png)
- Вы можете свободно:
- делиться произведением – копировать, распространять и передавать данное произведение
- создавать производные – переделывать данное произведение
- При соблюдении следующих условий:
- атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
- распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.
![]() |
Разрешается копировать, распространять и/или изменять этот документ в соответствии с условиями GNU Free Documentation License версии 1.2 или более поздней, опубликованной Фондом свободного программного обеспечения, без неизменяемых разделов, без текстов, помещаемых на первой и последней обложке. Копия лицензии включена в раздел, озаглавленный GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
История файла
Нажмите на дату/время, чтобы увидеть версию файла от того времени.
Дата/время | Миниатюра | Размеры | Участник | Примечание | |
---|---|---|---|---|---|
текущий | 09:15, 29 сентября 2010 | ![]() | 800 × 1200 (72 КБ) | Rocchini (обсуждение | вклад) | {{Information |Description={{en|1=The Chang Graphs. The Chang Graphs are strongly regular graphs with parameters (28,12,6,4). On the right the tree Chang Graphs; these graphs are generated by selecting a proper switching. On the left the originating [Tria |
Вы не можете перезаписать этот файл.
Использование файла
Следующая страница использует этот файл:
Глобальное использование файла
Данный файл используется в следующих вики:
- Использование в en.wikipedia.org
- Использование в es.wikipedia.org
- Использование в fr.wikipedia.org
- Использование в pt.wikipedia.org
- Использование в ru.wikipedia.org
- Использование в ta.wikipedia.org
- Использование в uk.wikipedia.org
- Использование в www.wikidata.org