第七章 图

第七章 神经组织总论组成神经细胞（神经元）神经胶质细胞功能神经元接受刺激、整合信息、传导冲动把接受的信息加以分析或贮存传递信息给各种肌细胞、腺细胞等效应细胞，以产生效应意识、记忆、思维和行为调节的基础神经胶质细胞支持、保护、营养和绝缘等参与神经递质和活性物质的代谢神经元神经元的结构胞体形态圆形，锥形，梭形和星形等分布位于灰质、皮质和神经节内功能神经元的营养和代谢中心光镜电镜结构细胞核位于胞体中央，大而圆核被膜明显着色浅，核仁大而圆细胞质特征性结构尼氏体神经原纤维两者不可在同一切片看到尼氏体强嗜碱性，HE染色紫蓝色均匀分布粗块状或小颗粒状有发达的粗面内质网和游离核糖体合成更新细胞器所需的结构蛋白、神经递质所需的酶类及肽类神经调质但是，不合成神经递质神经原纤维（嗜银纤维）HE染色切片无法分辨镀银染色呈棕黑色细丝，交错排列成网构成神经丝由神经丝蛋白构成的中间丝微管微管相关蛋白2构成神经元的细胞骨架，微管参与物质运输有脂褐素一种溶酶体的残余体细胞膜可兴奋膜双层脂质结构接受刺激、处理信息、产生并传导神经冲动树突每个神经元有一至多个树突内部结构同胞体有尼氏体和神经原纤维功能极大地扩展了神经元接受刺激的表面积轴突每个神经元有一条轴突无尼氏体，有神经原纤维、神经丝、微管、微丝比树突细无粗面内质网和游离核糖体神经丝、微管和微丝之间均有横桥连接， 构成轴质中的网架轴突运输（轴突内的物质运输）慢速轴突运输运输新形成的神经丝、微丝和微管快速顺向轴突运输快速逆向轴突运输神经元的分类按神经元的突起数量多极神经元双极神经元假单极神经元呈Ｔ形分为两支，周围突（分布到周围器官，接受刺激，具有树突的功能）和中枢突（进入中枢神经系统，传出冲动，为轴突）按神经元轴突的长短高尔基Ⅰ型神经元长轴突高尔基Ⅱ型神经元短轴突按神经元的功能感觉神经元（传入）多为假单极神经元运动神经元（传出）一般为多极神经元中间神经元主要为多极神经元学习、记忆和思维的基础按神经递质和调质的化学性质胆碱能神经元去甲肾上腺素能神经元胺能神经元氨基酸能神经元肽能神经元一氧化氮（NO）和一氧化碳（CO）也是一种神经递质突触概念神经元与神经元之间，或神经元与效应细胞之间传递信息的结构细胞连接方式轴-体突触轴-树突触轴-棘突触分类化学突触（人体主要）以神经递质作为传递信息的媒介HE染色不可分辨电突触缝隙连接，以电流作为信息载体存在于中枢神经系统和视网膜内的同类神经元之间化学性突触的结构 （电镜）突触前成分在镀银染色的切片呈棕黑色的圆形颗粒，称突触小体有线粒体、微丝和微管，无神经丝有突触小泡含神经递质或调质表面附有一种蛋白质，称突触素，将小泡连接干细胞骨架突触前膜较厚突触间隙15~30nm突触后成分突触后膜含有特异性的神经递质和调质的受体及离子通道突触的兴奋或抑制，取决于神经递质及其受体的种类Na+ → 兴奋Cl- → 抑制特点一个神经元可以通过突触把信息传递给许多其他神经元或效应细胞一个运动神经元可同时支配上千条骨骼肌纤维一个神经元也可以通过突触接受来自许多其他神经元的信息小脑的浦肯野细胞的树突上有数十万个突触神经胶质细胞功能支持、营养、保护和分隔神经元保证信息传递的专一性和不受干扰中枢神经系统胶质细胞HE染色中，除室管膜细胞外，都不易区分星形胶质细胞形态体积最大星形核圆或卵圆形胞质内含胶质丝（胶质原纤维酸性蛋白构成的中间丝）有些突起末端扩展形成脚板在脑和脊髓表面形成胶质界膜构成血－脑屏障的神经胶质膜功能支持和绝缘分泌神经营养因子和多种生长因子维持神经元的分化、功能，以及创伤后神 经元的可塑性变化组织损伤时，细胞增生形成胶质瘢痕少突胶质细胞分布神经元胞体附近及轴突周围形态胞体较小突起较少功能是中枢神经系统的髓鞘形成细胞（与施万细胞一起作用）小胶质细胞形态体积最小核小、染色深源于血液的单核细胞从两端发起突起功能中枢神经系统损伤时转变为巨噬细胞，具有吞噬作用室管膜细胞分布衬在脑室和脊髓中央管的腔面形态呈立方或柱状单层上皮游离面有微绒毛，少数细胞有纤毛功能参与产生脉络丛的脑脊液周围神经系统胶质细胞施万细胞参与周围神经系统中神经纤维的构成参与有髓神经纤维髓鞘形成分泌神经营养因子，促进受损的神经元存活及其轴突的再生卫星细胞有突起一层扁平或立方形细胞支持、保护、营养作用神经纤维和神经神经纤维构成神经元的长轴突神经胶质细胞根据神经胶质细胞是否形成髓鞘有髓神经纤维无髓神经纤维神经神经末梢。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第七章图习题答案基础知识：7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?答:(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图：(a)、(c)、(d)是连通图，(b)不是连通图，因为从1到2没有路径。

具体连通分量为：(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：(a)不是自由树，因为有回路。

(b)是自由森林，其两个连通分量为两棵自由树。

(c)不是自由树。

(d)是自由树。

7.2 在图7.24(下图)所示的有向图中：(1) 该图是强连通的吗? 若不是，则给出其强连通分量。

(2) 请给出所有的简单路径及有向环。

(3) 请给出每个顶点的度，入度和出度。

(4) 请给出其邻接表、邻接矩阵及逆邻接表。

答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。

(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)(3)每个顶点的度、入度和出度：D(v1)=3ID(v1)=1OD(v1)=2D(v2)=2 ID(v2)=1OD(v2)=1D(v3)=3 ID(v3)=2OD(v3)=1D(v4)=2 ID(v4)=1OD(v4)=1(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next┌─┬─┐┌─┬─┐┌─┬─┐0│v1│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘1│v2│─→│ 2│∧│├─┼─┤├─┼─┤2│v3│─→│ 0│∧│├─┼─┤├─┼─┤3│v4│─→│ 2│∧│└─┴─┘└─┴─┘逆邻接表：┌─┬─┐┌─┬─┐0│v1│─→│ 2│∧│├─┼─┤├─┼─┤1│v2│─→│ 0│∧│├─┼─┤├─┼─┤┌─┬─┐2│v3│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘3│v4│─→│ 0│∧│└─┴─┘└─┴─┘邻接矩阵：0 1 0 10 0 1 01 0 0 00 0 1 07.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。

第七章图一、选择题1、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。

A. nB. n2C. n-1D. (n-1)22、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A. 完全图B. 连通图C. 有回路D. 一棵树解析:在无向图中，如果从顶点v到顶点v1存在路径，则称v和v1是连通的。

完全图:若一个图的每一对不同顶点都恰有一条边相连。

3、关键路径是事件结点网络中（）。

A. 从源点到汇点的最长路径B. 从源点到汇点的最短路径C. 最长的回路D. 最短的回路4、下面（）可以判断出一个有向图中是否有环（回路）。

A. 广度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A. 第i行非无穷的元素之和B. 第i列非无穷的元素个数之和C. 第i行非无穷且非0的元素个数D. 第i行与第i列非无穷且非0的元素之和6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。

A. 中序遍历B. 先序遍历C. 后序遍历D. 按层次遍历7、无向图的邻接矩阵是一个（）。

A. 对称矩阵B. 零矩阵C. 上三角矩阵D. 对角矩阵8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（）。

A. N-2B. N-1C. ND. N+1当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为?解析:n+1 因为队列的头指针指向的是第一个元素的前一个结点，而不是指向第一个元素，因此队列的头指针要占用一个结点长度，所以队列的长度就是n+1;9、邻接表是图的一种（）。

A. 顺序存储结构B.链式存储结构C. 索引存储结构D. 散列存储结构10、下面有向图所示的拓扑排序的结果序列是（）。

A. 125634B. 516234C. 123456D. 52164313256411、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。