📄 page526.html
字号:
<HTML>
<HEAD>
<TITLE>Terminology</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html8419" HREF="page527.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page527.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8417" HREF="page524.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page524.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8411" HREF="page525.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8421" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8422" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0017102000000000000000">Terminology</A></H3>
<P>
Consider a directed graph <IMG WIDTH=72 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71355" SRC="img2282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2282.gif" > as given by Definition <A HREF="page525.html#defndigraph" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html#defndigraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<UL><LI>
Each element of <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71357" SRC="img2283.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2283.gif" > is called a <em>vertex</em><A NAME=48789> </A>
or a <em>node</em><A NAME=48791> </A> of <I>G</I>.
Hence, <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71357" SRC="img2283.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2283.gif" > is the set of <em>vertices</em> (or <em>nodes</em>) of <I>G</I>.<LI>
Each element of <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71363" SRC="img2284.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2284.gif" > is called an <em>edge</em><A NAME=48795> </A>
or an <em>arc</em> of <I>G</I>.
Hence, <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71363" SRC="img2284.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2284.gif" > is the set of <em>edges</em> (or <em>arcs</em>) of <I>G</I>.<LI>
An edge <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71405" SRC="img2290.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2290.gif" > can be represented as <IMG WIDTH=44 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline71407" SRC="img2291.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2291.gif" >.
An arrow that points from <I>v</I> to <I>w</I> is known
as a <em>directed arc</em><A NAME=48800> </A><A NAME=48801> </A>.
Vertex <I>w</I> is called the <em>head</em> of the arc
because it is found at the arrow head.
Conversely, <I>v</I> is called the <em>tail</em> of the arc.
Finally, vertex <I>w</I> is said to be <em>adjacent</em><A NAME=48805> </A>
to vertex <I>v</I>.<LI>
An edge <I>e</I>=(<I>v</I>,<I>w</I>) is said to
<em>emanate</em><A NAME=48807> </A><A NAME=48808> </A> from vertex <I>v</I>.
We use notation <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71425" SRC="img2292.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2292.gif" > to denote the set of edges
emanating from vertex <I>v</I>.
I.e., <IMG WIDTH=210 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71429" SRC="img2293.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2293.gif" ><LI>
The <em>out-degree</em><A NAME=48810> </A><A NAME=48811> </A>
of a node is the number of edges
emanating from that node.
Therefore, the out-degree of <I>v</I> is <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71433" SRC="img2294.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2294.gif" ><LI>
An edge <I>e</I>=(<I>v</I>,<I>w</I>) is said to be
<em>incident</em><A NAME=48813> </A><A NAME=48814> </A> on vertex <I>w</I>.
We use notation <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71439" SRC="img2295.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2295.gif" > to denote the set of edges
incident on vertex <I>w</I>.
I.e., <IMG WIDTH=215 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71443" SRC="img2296.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2296.gif" ><LI>
The <em>in-degree</em><A NAME=48816> </A><A NAME=48817> </A>
of a node is the number of edges
incident on that node.
Therefore, the in-degree of <I>w</I> is <IMG WIDTH=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71447" SRC="img2297.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2297.gif" ></UL>
<P>
For example, Table <A HREF="page526.html#tblgraph1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page526.html#tblgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> enumerates the sets of
emanating and incident edges
and the in- and out-degrees
for each of the vertices in graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif" > shown in Figure <A HREF="page525.html#figgraph1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="48886"> </A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -