File:Critical graph sample.svg
Материал из Викисклада, хранилища свободных медиафайлов
Перейти к навигации
Перейти к поиску
Размер этого PNG-превью для исходного SVG-файла: 600 × 600 пкс. Другие разрешения: 240 × 240 пкс | 480 × 480 пкс | 768 × 768 пкс | 1024 × 1024 пкс | 2048 × 2048 пкс.
Исходный файл (SVG-файл, номинально 600 × 600 пкс, размер файла: 17 КБ)
Сведения о файле
Структурированные данные
Краткие подписи
Содержание
Краткое описание
[править]ОписаниеCritical graph sample.svg |
English: Example of Vertex Critical Graph: on the left-top the original vc08-chi06 with chromatic number=6, next all the N-1 subgraphs with chromatic number= 5 |
Дата | |
Источник | Собственная работа |
Автор | Claudio Rocchini |
Thanks
[править]Many thanks to Gordon Royles [1] for the graph example.
Source Code
[править]Dirty C++ generating code:
/* (C)2013 Claudio Rocchini CC-BY 3.0 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <algorithm>
const double PI = 3.1415926535897932384626433832795;
typedef std::pair<int,int> edge;
int greedy_color( int N, const std::vector<edge> & edges, std::vector<int> & colors ) {
std::vector< std::vector<int> > stars(N);
std::vector<edge>::const_iterator ii;
for(ii=edges.begin();ii!=edges.end();++ii) {
stars[(*ii).first ].push_back( (*ii).second );
stars[(*ii).second].push_back( (*ii).first );
}
colors.resize(N);
for(int nc=2;;++nc) {
std::fill(colors.begin(),colors.end(),-1); colors[0] = 0;
int p = 1;
for(;;) {
if(++colors[p]==nc) {
colors[p] = -1;
if(--p<1) break; else continue;
}
std::vector<int>::const_iterator jj;
for(jj=stars[p].begin();jj!=stars[p].end();++jj)
if(colors[*jj]==colors[p]) break;
if(jj==stars[p].end()) if(++p==N) break;
}
if(p==N) return nc;
}
}
int main() {
const int S = 600;
const int rgb[][3] = {
{255,8,8},{8,255,8},{8,8,255},{255,255,8},{255,8,255},{255,255,255}
};
/* Than's to for this graph:
http://school.maths.uwa.edu.au/~gordon/remote/graphs/ */
const int N = 8;
const int pe[N] = {0,2,4,1,3,5,6,7};
const int gr[N][7]= {
{2,3,5,6,7,-1,-1}, {3,4,5,6,7,-1,-1}, {0,4,5,6,7,-1,-1},
{0,1,5,6,7,-1,-1}, {1,2,5,6,7,-1,-1},
{0,1,2,3,4,6,7}, {0,1,2,3,4,5,7}, {0,1,2,3,4,5,6}
};
int i,j,k;
const double R1=S/7, R2=R1*2/3, R3=8;
double x[N],y[N];
for(i=0;i<5;++i) {
x[pe[i]] = +sin(2*PI*i/5)*R1;
y[pe[i]] = -cos(2*PI*i/5)*R1;
}
for(i=0;i<3;++i) {
x[i+5] = +sin(2*PI*i/3)*R2;
y[i+5] = -cos(2*PI*i/3)*R2;
}
FILE * fo = fopen("critical.svg","w");
fprintf(fo,
"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
"<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.0\" width=\"%d\" height=\"%d\" id=\"criticalg\">\n"
,S,S
);
for(k=-1;k<N;++k) {
double lx = S/6+((k+1)%3)*S/3; double ly = S/6+((k+1)/3)*S/3;
std::vector<edge> edges;
for(i=0;i<N;++i) if(i!=k)
for(j=0;j<7;++j)
if(gr[i][j]>i && gr[i][j]!=k)
edges.push_back( edge(i,gr[i][j]) );
std::vector<int> colors;
int nc = greedy_color(N,edges,colors);
printf("colors = %d\n",nc);
fprintf(fo,"<g style=\"stroke:#000000;stroke-width:1.5;fill:none\">\n");
for(i=0;i<int(edges.size());++i)
if(edges[i].first!=k && edges[i].second!=k)
fprintf(fo,"<line x1=\"%6.2f\" y1=\"%6.2f\" x2=\"%6.2f\" y2=\"%6.2f\"/>\n"
,lx+x[edges[i].first ],ly+y[edges[i].first]
,lx+x[edges[i].second],ly+y[edges[i].second]
);
fprintf(fo,"</g>\n");
fprintf(fo,"<g>\n");
for(i=0;i<N;++i) if(i!=k)
fprintf(fo,"<circle cx=\"%6.2f\" cy=\"%6.2f\" r=\"%g\" "
"style=\"stroke:#000000;stroke-width:1;stroke-opacity:1.0;fill:#%02X%02X%02X\"/>\n"
,lx+x[i],ly+y[i],R3
,rgb[colors[i]][0],rgb[colors[i]][1],rgb[colors[i]][2]
);
fprintf(fo,"</g>\n");
}
fprintf(fo,"</svg>\n");
fclose(fo);
return 0;
}
Лицензирование
[править]Я, владелец авторских прав на это произведение, добровольно публикую его на условиях следующей лицензии:
Этот файл доступен по лицензии Creative Commons Attribution-Share Alike 3.0 Unported.
- Вы можете свободно:
- делиться произведением – копировать, распространять и передавать данное произведение
- создавать производные – переделывать данное произведение
- При соблюдении следующих условий:
- атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
- распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.
История файла
Нажмите на дату/время, чтобы увидеть версию файла от того времени.
Дата/время | Миниатюра | Размеры | Участник | Примечание | |
---|---|---|---|---|---|
текущий | 11:52, 4 июня 2013 | 600 × 600 (17 КБ) | Rocchini (обсуждение | вклад) | User created page with UploadWizard |
Вы не можете перезаписать этот файл.
Использование файла
Следующая страница использует этот файл:
Глобальное использование файла
Данный файл используется в следующих вики:
- Использование в en.wikipedia.org
- Использование в hr.wikipedia.org
- Использование в hu.wikipedia.org
- Использование в ru.wikipedia.org
- Использование в uk.wikipedia.org
- Использование в www.wikidata.org
Метаданные
Файл содержит дополнительные данные, обычно добавляемые цифровыми камерами или сканерами. Если файл после создания редактировался, то некоторые параметры могут не соответствовать текущему изображению.
Ширина | 600 |
---|---|
Высота | 600 |