Ficheiro:Chang graphs.svg

O conteúdo da página não é suportado noutras línguas.
Origem: Wikipédia, a enciclopédia livre.

Imagem numa resolução maior ‎(ficheiro SVG, de 800 × 1 200 píxeis, tamanho: 72 kB)

Descrição do ficheiro

Descrição
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.
Data
Origem Obra do próprio
Autor Claudio Rocchini
Permissão
(Reutilizar este ficheiro)		 CC-BY 3.0

References

Many thanks to Nadia Hamoudi for paper "The Chang graphs" at Nadia Hamoudi "The Chang graphs" cópia arquivada 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;
}

Licenciamento

Eu, titular dos direitos de autor desta obra, publico-a com as seguintes licenças:
w:pt:Creative Commons
atribuição partilha nos termos da mesma licença
A utilização deste ficheiro é regulada nos termos da licença Creative Commons - Atribuição-CompartilhaIgual 3.0 Não Adaptada.
Pode:
  • partilhar – copiar, distribuir e transmitir a obra
  • recombinar – criar obras derivadas
De acordo com as seguintes condições:
  • atribuição – Tem de fazer a devida atribuição da autoria, fornecer uma hiperligação para a licença e indicar se foram feitas alterações. Pode fazê-lo de qualquer forma razoável, mas não de forma a sugerir que o licenciador o apoia ou subscreve o seu uso da obra.
  • partilha nos termos da mesma licença – Se remisturar, transformar ou ampliar o conteúdo, tem de distribuir as suas contribuições com a mesma licença ou uma licença compatível com a original.
GNU head É concedida permissão para copiar, distribuir e/ou modificar este documento nos termos da Licença de Documentação Livre GNU, versão 1.2 ou qualquer versão posterior publicada pela Free Software Foundation; sem Secções Invariantes, sem textos de Capa e sem textos de Contra-Capa. É incluída uma cópia da licença na secção intitulada GNU Free Documentation License.
Pode escolher a licença que quiser.

Legendas

Adicione uma explicação de uma linha do que este ficheiro representa

Elementos retratados neste ficheiro

retrata

tipo de média

image/svg+xml

soma de verificação

7b6c7a81bb8fea0ec0d28f8ad20fee2fba387290

método de determinação: SHA-1

tamanho dos dados

73 627 byte

altura

1 200 pixel

largura

800 pixel

Histórico do ficheiro

Clique uma data e hora para ver o ficheiro tal como ele se encontrava nessa altura.

Data e horaMiniaturaDimensõesUtilizadorComentário
atual09h15min de 29 de setembro de 2010Miniatura da versão das 09h15min de 29 de setembro de 2010800 × 1 200 (72 kB)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

A seguinte página usa este ficheiro:

Utilização global do ficheiro

As seguintes wikis usam este ficheiro:

Obtida de "https://pt.wikipedia.org/wiki/Ficheiro:Chang_graphs.svg"