6 �O���t

�O���t(graph)$G=(V,E)$���C���_(vertex)�����������L���W��$V$����(edge)�� �W��$E$�����������������������������������D �������_��������$(v,w)$���^���������������C�����O���t�� �L��(directed)�O���t�����������D$v$��$(v,w)$���n�_(head)�C$w$���I�_(tail)�������D �������������������_��������������$(v,w)$���O�� �t������(undirected)�O���t�����������D ������������������������������$(a,a)$���L���O���t�������������C�����O���t �������������D �O���t$G=(V,E)$��������$(v,w)$��$E$�����������������C���_$w$�����_ $v$�������iadjacent)���������������D���_$v$�������������_�������� $v$�������idegree)�������D

• ��(path) ���i�p�X�j���� $(v_1,v_2),(v_2,v_3),...,(v_{n-1},v_{n})$�������`������ �������������������D���������C$v_{1}$����$v_{n}$���������������C������ ����$n-1$�������������D�P�������_�������O�����������D�P��(simple) ���������C�����������_�����������������������������D���H(cycle) �����C�������_�����n�����������_���I�������������P�������P������������ �������D�����O���t�������H���������R�����������D �O���t�������Q�_$u$,$v$����������$u$����$v$���p�X�����������C�����O�� �t���A��(connected)�����������������D
• �����s��(adjacency matrix) �O���t���\�����@�������D�O���t$G=(V,E)$�������s��$A$���C�W��$V$���v�f ������$\vert\vert V\vert\vert$���������s���������C�v�f��0������1�������������D$G$���� $(i,j)$�����������������C$A[i,j]=1$�������D�����������������������p�� �������������������L�������C�L��������${\vert\vert V\vert\vert}^2$�K�v�����������s���� �����l���^���������������������������������D�s�����������r�b�g�x�N�g�� ���\���������@�������D
• �����_���X�g(adjacency list) ���_$v$�������_���X�g�����C$v$���������������������_$w$�����X�g�������������D �L��������$\vert\vert V\vert\vert+\vert\vert E\vert\vert$�����������D $\vert\vert E\vert\vert << {\vert\vert V\vert\vert}^2$�����������g�������D