简单无向图的压缩存储及格式转换算法  

The compact storage of simple undirected graphs and its format conversion algorithm

作　　者：刘治国[1] 

机构地区：[1]北京联合大学信息学院,北京100101

出　　处：《信息技术》2013年第11期88-91,共4页Information Technology

基　　金：北京市教委科技面上项目(KM201111417015)

摘　　要：对于图的同构判定问题、Ramsey理论、计算Folkman数等图论的研究方向,研究人员通常需要用计算机程序生成并处理大量的简单无向图。为了节省内存和外存空间、提高程序运行速度,应该对图进行压缩存储。文中对目前研究中广泛采用的简单无向图graph6存储格式进行了介绍,并给出了将图的邻接表存储格式转换为graph6存储格式的程序片段。For some research directions of graph theory,such as isomorphism testing problem for graphs,Ramsey theory,computing the Folkman number,researchers usually need to generate and process a mess of simple undirected graphs by using computer programs.In order to save internal memory and external storage space,improve the running speed of these programs,graphs should be stored in a compact way.This article introduces the graph6 storage format of simple undirected graphs,which is widely used in related research fields now.Also,it presents the program fragment for conversion from adjacent list to graph6 storage format.

关 键 词：简单无向图 压缩存储 graph6 图存储格式的转换 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]