typedef byte SetOfVertices[(MAXVERTICES%8)?((MAXVERTICES/8)+1):(MAXVERTICES/8)];
/***********************************
Danh sach da lien ket cho cac canh
***********************************/
typedef struct EdgeNode *EdgePointer;
struct EdgeNode
{
byte Vertex[2];
EdgePointer Link[2];
};
typedef struct
{
char Data;
EdgePointer Next;
} ListEdge;
typedef ListEdge *ListEdgePointer;
typedef ListEdgePointer ArrayOfEdge[MAXVERTICES];
/***** Phan khai bao prototype ham *****/
void Create(AdjPointer *List);
Boolean Empty(AdjPointer List);
void Push(AdjPointer *List, byte Item);
void Pop(AdjPointer *List, byte *Item);
void CreatQueue(Queue *Q);
Boolean EmptyQueue(Queue Q);
void PushQueue(Queue *Q, byte Item);
void PopQueue(Queue *Q, byte *Item);
Boolean EmptySet(SetOfVertices S);
Boolean InSet(SetOfVertices S, byte Value);
void InitSet(SetOfVertices S, byte MaxValue);
void AddSet(SetOfVertices S, byte Value);
void SubSet(SetOfVertices S, byte Value);

AdjPointer TempPtr;
if (Empty(*List))
{
printf(" Thao tac con tro khong hop le ");
return;
200
}
TempPtr = (*List);
(*Item) = TempPtr->Vertex;
(*List) = TempPtr->Next;
free(TempPtr);
}
void CreatQueue(Queue *Q)
{
(*Q).Head = NULL;
}
Boolean EmptyQueue(Queue Q)
{
return((Q.Head == NULL) ? TRUE : FALSE);
}
void PushQueue(Queue *Q, byte Item)
{
QueueNode TempPtr;
TempPtr = (QueueNode) malloc(sizeof(struct QueueType));
TempPtr->Vertex = Item;
TempPtr->Next = NULL;
if ((*Q).Head == NULL) (*Q).Head = TempPtr;
else (*Q).Tail->Next = TempPtr;
(*Q).Tail = TempPtr;
}

if (MaxValue>MAXVERTICES)
{
printf(" Gia tri khong thuoc tap hop ");
return;
}
for (i = 0; i < MaxValue; i++) S[i/8] |= 0x80 >> (i%8);
}
void AddSet(SetOfVertices S, byte Value)
{
int i;
if ((Value < 1) || (Value > MAXVERTICES))
{
printf(" Gia tri khong thuoc tap hop ");
return;
}
202
S[(Value-1)/8] |= 0x80 >> ((Value-1)%8);
}
void SubSet(SetOfVertices S, byte Value)
{
if ((Value < 1) || (Value > MAXVERTICES))
{
printf(" Gia tri khong thuoc tap hop ");
return;
}
S[(Value-1)/8] &= ~(0x80 >> ((Value-1)%8));
}
int feoln(FILE *fp)
{
char c;

}
NumVert = 0;
while (!feof(FileData))
{
HeadPtr = (HeadPointer) malloc(sizeof(HeadNode));
HeadPtr->Next = NULL;
fgets(HeadPtr->Data, MAXSTRINGS+1, FileData);
// Ham fgets(char *s, int n, FILE *fp) chi doc n-1 ky tu
while (!feoln(FileData))
{
VerPtr = (AdjPointer) malloc(sizeof(struct VertexNode));
fscanf(FileData, "%d", &(VerPtr->Vertex));
if (Weight)
{
fscanf(FileData, "%d", &(VerPtr->Length));
VerPtr->Flow = 0;
}
VerPtr->Next = HeadPtr->Next;
HeadPtr->Next = VerPtr;
}
freadln(FileData);
++NumVert;
V_out[NumVert] = HeadPtr;
}
(*NumVertices) = NumVert;
fclose(FileData);
}
void MakeV_in(char *FileName, ArrayOfPointer V_in, ArrayOfPointer V_out,
byte *NumVertices);
{

}
}
void BuildGraph(char *FileName, ArrayOfEdge E, byte *NumVertices)
{
byte EndPt, NumVert;
int i;
char ch[2];
EdgePointer EdgePtr;
FILE *FileData;
if ((FileData = fopen(FileName, "rt")) == NULL)
{
205
printf(" File khong tim thay ");
return;
}
NumVert = 0;
while (!feoln(FileData))
{
++NumVert;
E[NumVert] = (ListEdgePointer) malloc(sizeof(ListEdge));
fscanf(FileData, "%s", ch);
E[NumVert]->Data = ch[0];
E[NumVert]->Next = NULL;
}
(*NumVertices) = NumVert;
for (i=1; i<=NumVert; i++) printf("%c ", E[i]->Data);
printf("\n");
freadln(FileData);
while (!feof(FileData))
{

NewStart = Ptr->Vertex[OtherEnd];
if (InSet(Unvisited, NewStart)) DFS(E, NewStart, Unvisited);
Ptr = Ptr->Link[StartEnd];
}
}
void DisplayV_out(ArrayOfPointer V_out, byte NumVertices, Boolean Weight)
{
int i;
AdjPointer CurrPtr;
for (i=1; i<=NumVertices; i++)
{
printf("(%d) %s ", i, V_out[i]->Data);
CurrPtr = V_out[i]->Next;
while (CurrPtr!=NULL)
{
printf("%d ", CurrPtr->Vertex);
if (Weight) printf("%d ", CurrPtr->Length);
CurrPtr = CurrPtr->Next;
}
printf("\n");
}
printf("\n");
}
void DisplayV_in(ArrayOfPointer V_in, byte NumVertices)
{
int i;
AdjPointer CurrPtr;
for (i=1; i<=NumVertices; i++)
207
{

#endif
208
T`ai liˆe
.
u tham kha
˙’
o
[1] Appel K., The proof of the four-colour problem, New Scientist. 72, 154-155 (1976).
[2] Arlinghaus S., Arlinghaus W., Nystuen J., The Hedetniemi matrix sum: an algorithm
for shortest path and shortest distance, Geographical Analysis, Vol. 22, No. 4, Oct.,
351-360 (1990).
[3] Bellman R., On a routing problem, Quart. of Applied Mathematics, 16, 87 (1958).
[4] Berge C., L´y thuyˆe
´
t d¯ˆo
`
thi
.
v`a ´u
.
ng du
.
ng, NXB Khoa ho
.
c v`a K˜y thuˆa
.
t H`a Nˆo
.
i, 1971.
[5] Berge C., Two theorems in graph theory, Proc. Nat. Ac. Sc., 43, 842 (1957).

[24] Fary I., On straight line representation of planar graphs, Acta Sci. Math. Szeged, Vol.
11, 229-293 (1948).
[25] Floyd R. W., Algorithm 97-Shortest path, Comm. of ACM, 5, 345 (1962).
[26] Ford L. R. Jr., Network flow theory, Rand Corporation Report 923 (1946).
[27] Ford L. R., Fulkerson D. R., Flows in networks, Princeton University Press, Princeton
(1962).
[28] Gilbert E. N., Pollack H. O., Steiner minimal trees, Jl. of SIAM (Appl. Math.), 16 1
(1968).
[29] Gomory R. E., Hu T. C., Synthesis of a communication network, Jl. of SIAM (App.
Math.), 12 348 (1964).
[30] Gondran M., Minoux M., Vajda S., Graphs and algorithms, John Wiley & Sons (1990).
[31] Hamming R. W., Coding and information theory, Prentice Hall (1980).
[32] Hanan M., On Steiner’s problem with rectilinear distance, Jl. of SIAM (Appl. Math.),
14 255 (1966).
210
[33] Hopcroft J. E., Tarjan R. E., Isomorphism of planar graphs, in Complexity of Computer
Computations, Plenum, New York (1972).
[34] Hopcroft J. E., Tarjan R. E., Efficient planarity testing, J. ACM 21, 549-568 (1974).
[35] Hu T. C., Integer programming and network flows, Addison-Wesley, Reading, Mas-
sachusetts (1969).
[36] Kerchenbaum A., Van Slyke R., Computing minimum spanning trees efficiently, Proc.
of the Ann. Conf. of ACM, Boston, 518 (1972).
[37] Kirchhoff G., in “Annalen der Physik and Chemie” 72, 497 (1847).
[38] Klein M., A primal method for minimal cost flows with applications to the assignment
and transportation problems, Man. Sci., 14, 205 (1967).
[39] Kruskal J. B. Jr., On the shortest spanning subtree of a graph and the traveling salesman
problem, Proc. American Mathematical Soc., 7, 48 (1956).
[40] Kraitchik M., Le probl`eme des Reines, Bruxelles (1926).
[41] Kevin V., Whitney M., Algorithm 422-Minimum spanning tree, Comm. of ACM, 15,
273 (1972).

[52] Shirey R. W., Implementation and analysis of efficient graph planarity testing algo-
rithms, Ph.D. Dissertation, Computer Sciences, University of Wisconsin, Madison,
Wisc. (1969).
[53] Tarjan R., Depth-first search and linear graph algorithms, SIAM J. Computer 1 146-160
(1972).
[54] Tutte W. T., How to draw graph, Proc. London Math. Soc., Ser. 3, Vol. 13, 743-768
(1963).
[55] Whitney H., 2−Isomorphic graphs, Am. J. Math. Vol. 55 245-254 (1933).
212