Ir al contenido

Archivo:Chang graphs.svg

Contenido de la página no disponible en otros idiomas.
De Wikipedia, la enciclopedia libre

Ver la imagen en su resolución original ‎((Imagen SVG, nominalmente 800 × 1200 pixels, tamaño de archivo: 72 kB))

Este es un archivo de Wikimedia Commons, un depósito de contenido libre hospedado por la Fundación Wikimedia. Más abajo se reproduce su página de descripción con la información sobre su origen y licencia.

Resumen

Descripción
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.
Fecha
Fuente Trabajo propio
Autor Claudio Rocchini
Permiso
(Reutilización de este archivo)		 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;
}

Licencia

Yo, titular de los derechos de autor de esta obra, la publico en los términos de las siguientes licencias:
w:es:Creative Commons
atribución compartir igual
Este archivo se encuentra bajo la licencia Creative Commons Genérica de Atribución/Compartir-Igual 3.0.
Eres libre:
  • de compartir – de copiar, distribuir y transmitir el trabajo
  • de remezclar – de adaptar el trabajo
Bajo las siguientes condiciones:
  • atribución – Debes otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si realizaste algún cambio. Puedes hacerlo de cualquier manera razonable pero no de manera que sugiera que el licenciante te respalda a ti o al uso que hagas del trabajo.
  • compartir igual – En caso de mezclar, transformar o modificar este trabajo, deberás distribuir el trabajo resultante bajo la misma licencia o una compatible como el original.
GNU head Se autoriza la copia, distribución y modificación de este documento bajo los términos de la licencia de documentación libre GNU, versión 1.2 o cualquier otra que posteriormente publique la Fundación para el Software Libre; sin secciones invariables, textos de portada, ni textos de contraportada. Se incluye una copia de la dicha licencia en la sección titulada Licencia de Documentación Libre GNU.
Puedes usar la licencia que prefieras.

Leyendas

Añade una explicación corta acerca de lo que representa este archivo

Elementos representados en este archivo

representa a

tipo de archivo

image/svg+xml

suma de verificación

7b6c7a81bb8fea0ec0d28f8ad20fee2fba387290

método de determinación: SHA-1

altura

1200 píxel

ancho

800 píxel

Historial del archivo

Haz clic sobre una fecha y hora para ver el archivo tal como apareció en ese momento.

Fecha y horaMiniaturaDimensionesUsuarioComentario
actual09:15 29 sep 2010Miniatura de la versión del 09:15 29 sep 2010800 × 1200 (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

La siguiente página usa este archivo:

Uso global del archivo

Las wikis siguientes utilizan este archivo:

Obtenido de «https://es.wikipedia.org/wiki/Archivo:Chang_graphs.svg»