Файл:Chang graphs.svg
Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації
Перейти до пошуку
Розмір цього попереднього перегляду PNG для вихідного SVG-файлу: 400 × 600 пікселів. Інші роздільності: 160 × 240 пікселів | 320 × 480 пікселів | 512 × 768 пікселів | 682 × 1024 пікселів | 1365 × 2048 пікселів.
Повна роздільність (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;
}
Ліцензування
Я, власник авторських прав на цей твір, добровільно публікую його на умовах таких ліцензій:
Цей файл ліцензований на умовах ліцензії Creative Commons Attribution-Share Alike 3.0 Unported
- Ви можете вільно:
- ділитися – копіювати, поширювати і передавати твір
- модифікувати – переробляти твір
- При дотриманні таких умов:
- зазначення авторства – Ви повинні вказати авторство, надати посилання на ліцензію і вказати, чи якісь зміни було внесено до оригінального твору. Ви можете зробити це в будь-який розсудливий спосіб, але так, щоб він жодним чином не натякав на те, наче ліцензіар підтримує Вас чи Ваш спосіб використання твору.
- поширення на тих же умовах – Якщо ви змінюєте, перетворюєте або створюєте іншу похідну роботу на основі цього твору, ви можете поширювати отриманий у результаті твір тільки на умовах такої ж або сумісної ліцензії.
Дозволяється копіювати, розповсюджувати та/або модифікувати цей документ на умовах ліцензії GNU FDL версії 1.2 або більш пізньої, виданої Фондом вільного програмного забезпечення, без незмінних розділів, без текстів, які розміщені на першій та останній обкладинці. Копія ліцензії знаходиться у розділі GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Ви можете обрати ліцензію на ваш розсуд.
Об'єкти, показані на цьому файлі
зображує
Якесь значення без елемента на сайті Вікідані
29 вересня 2010
image/svg+xml
7b6c7a81bb8fea0ec0d28f8ad20fee2fba387290
73 627 байт
1200 піксель
800 піксель
Історія файлу
Клацніть на дату/час, щоб переглянути, як тоді виглядав файл.
Дата/час | Мініатюра | Розмір об'єкта | Користувач | Коментар | |
---|---|---|---|---|---|
поточний | 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
- Використання в www.wikidata.org