高等代数中有关问题的降价算法

1 行列式值的计算求行列式值常用的计算方法[1]多种多样,但对高阶行列式计算很少有通用的公式．在计算机普及的条件下,公式法显得尤为重要,下面给出一种简单易行的公式法--降阶算法,它充分利用了二阶行列式计算简单、可以心算的特点,逐次降阶而又不增子行列式计算的个数,减少了计算量又易于上机,从而提高了计算速度．     

行列式的几何意义及多面体体积的计算

通过引入体积坐标证明了行列式和多面体体积的关系,使得每一个行列式都有了它的几何解释,有助于形象地理解行列式的概念,并利用行列式的几何意义计算空间多面体的体积.     

从几何直观的视角理解行列式

行列式理论是线性代数课程的一个重要内容.从平行四边形的有向面积、平行六面体的有向体积以及它们的几何直观性质引进低阶行列式的定义,可以帮助学习者从几何直观的角度更好地理解行列式的定义以及行列式的性质.克莱姆法则、矩阵乘积的行列式以及代数余子式等代数概念都可以进行几何直观的解释.     

介绍两种行列式的计算方法

<正> 在高等代数课程中,n阶行列式的计算是一个主要内容。但是n阶行列式的计算还没有一个普遍适用的方法、在处理特殊类型的行列式有各种不同的方法。本文将给出:两种行列式的计算方法,使用这两种方法不仅可以解决用其他方法难以计算出的行列式,并且极大简化     

介绍一种用公式计算行列式的方法

在高等代数课程中,对n阶行列式的计算,一般方法是不存在的,但处理特殊类型的行列式有各种不同的方法。本文介绍一种用公式计算行列式的方法,这种计算方法对某种n阶行列式是较为有用的一种方法,它适用于较复杂     

行列式的几种常用算法

计算一个n阶行列式有时是颇为麻烦的。但是,只要熟悉行列式的一般性质,在动手计算行列式之前,先考查所要计算的行列式的一些特点,再决定算法,算起来却也不很困难。这里,我们将一般常用的算法归纳如下,以资参考。 1.三角化。这种方法主要是根据行列式的下述简单性质进行的:在计算行列式时,可以先对行列式适当地进行行或列的初等变换,尽量设法将所要计算的行列式化为上(下)三角形式,这样就能将行列式算出来。     

美国Putnam数学竞赛中两道行列式证明题的泰勒公式解法

介绍了美国Putnam数学竞赛中两道行列式证明题的分析证明方法.选取行列式中的某个参数(常数)为变量,使得行列式可设为该变量的多项式,然后分别计算函数值和各阶导数值,进而利用泰勒展式即可计算出行列式的值.     

一类含参行列式的思考

本文给出了一种简化一类n阶行列式计算的参数方法.先通过引入参数t_i(i≤n),构造参数t_i(i≤n)的行列式,且从理论上证明了它是关于t_i(i≤n)的线性函数;再通过待定系数法,确定这个线性函数,从而得到关于参数t_i(i≤n)的行列式值,进而求得所要计算的行列式;最后,利用此式还给出了求行列式的代数余子式之和的简洁计算方法.     

关于行列式计算的另类降阶法

由于二阶行列式的计算仅须求两对角线元素的乘积之差,所以计算非常简单．一般地,对高阶行列式求值,虽然可用Laplace展开公式或Gauss消去法,但是展开式会非常繁杂或计算量会很大．本文利用降阶原理,得到一种只需计算二阶行列式就可求出n（n≥3）阶方阵行列式值的另类方法．     

介绍一种用四分块矩阵计算n阶行列式的方法

介绍一种用四分块矩阵计算n阶行列式的方法,这种计算方法对某些n阶行列式是较为有用的一种方法,它适用于比较复杂特殊的行列式.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

Decompositions of digraphs into paths and cycles

It is shown that in a digraph G, there is an elementary directed path or an elementary directed cycle meeting all inclusion-maximal demi-cocycles of G. This theorem is used to obtain an upper bound on the cardinality of a minimal partition of the arc set of G into directed paths and cycles.     

On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

Cycles and paths in semicomplete multipartite digraphs,theorems, and algorithms: a survey

A digraph obtained by replacing each edge of a complete m-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is calied a semicomplete m-partite digraph. We describe results (theorems and algorithms) on directed walks in semicomplete m-partite digraphs, including some recent results concerning tournaments. © 1995 John Wiley & Sons, Inc.     

若干有向图的SAS-全染色

提出了有向图的SAS-全染色的概念,有向图D的SAS-全染色是D的一个正常全染色,若对D中点染色来说,不存在长为3的2色有向路.对D中弧染色来说,不存在长为4的2色有向路.并定义了有向图D的SAS-全色数,记为(D).用构造染色的方法给出了一些特殊有向图(有向路,有向圈,定向轮,定向扇,有向双星)的SAS-全色数.     

Finding coherent cyclic orders in strong digraphs

A cyclic order in the vertex set of a digraph is said to be coherent if any arc is contained in a directed cycle whose winding number is one. This notion plays a key role in the proof by Bessy and Thomassé (2004) of a conjecture of Gallai (1964) on covering the vertex set by directed cycles. This paper presents an efficient algorithm for finding a coherent cyclic order in a strongly connected digraph, based on a theorem of Knuth (1974). With the aid of ear decomposition, the algorithm runs in O(nm) time, where n is the number of vertices and m is the number of arcs. This is as fast as testing if a given cyclic order is coherent.     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.