2011年1月12日 星期三
2010年12月17日 星期五
multigraph
From Wikipedia, the free encyclopedia
This article is about the mathematical concept. For other uses, see Multigraph (disambiguation).
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, (also called "parallel edges"[1]), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. Formally, a multigraph G is an ordered pair G:=(V, E) with
Multigraphs might be used to model the possible flight connections offered by an airline. In this case the multigraph would be a directed graph with pairs of directed parallel edges connecting cities to show that it is possible to fly both to and from these locations.
Some authors also allow multigraphs to have loops, that is, an edge that connects a vertex to itself,[2] while others call these pseudographs, reserving the term multigraph for the case with no loops.[3]
A multidigraph is a directed graph which is permitted to have multiple arcs, i.e., arcs with the same source and target nodes. A multidigraph G is an ordered pair G:=(V,A) with
- V a set of vertices or nodes,
- A a multiset of ordered pairs of vertices called directed edges, arcs or arrows.
In category theory a small category can be defined as a multidigraph equipped with an associative composition law and a distinguished self-loop at each vertex serving as the left and right identity for composition. For this reason, in category theory the term graph is standardly taken to mean "multidigraph", and the underlying multidigraph of a category is called its underlying digraph.
A mixed multigraph G:=(V,E, A) may be defined in the same way as a mixed graph.
Strongly connected component
Strongly connected component
From Wikipedia, the free encyclopedia
A directed graph is called strongly connected if there is a path from each vertex in the graph to
every other vertex. In particular, this means paths in each direction; a path from a to b and also
a path from b to a.
The strongly connected components of a directed graph G are its maximal strongly connected subgraphs.
If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph,
the condensation of G. A directed graph is acyclic if and only if it has no (nontrivial) strongly connected subgraphs
(because a cycle is strongly connected, and every strongly connected graph contains at least one cycle).
Kosaraju's algorithm, Tarjan's algorithm and Gabow's algorithm all efficiently compute the strongly connected
components of a directed graph, but Tarjan's and Gabow's are favoured in practice since they require only one
depth-first search rather than two.
Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems
(systems of Boolean variables with constraints on the values of pairs of variables): as Aspvall, Plass & Tarjan (1979)
showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its complement
are both contained in the same strongly connected component of the implication graph of the instance.
2010年12月12日 星期日
SSH、SSL
SSH為Secure Shell的縮寫，由IETF的網路工作小組（Network Working Group）所制定；SSH為建立在應用層和傳輸層基礎上的安全協定。
傳統的網路服務程式，如FTP、POP和Telnet其本質上都是不安全的；因為它們在網路上用明文傳送資料、使用者帳號和使用者口令，很容易受到中間人（man-in-the-middle）攻擊方式的攻擊。就是存在另一個人或者一台機器冒充真正的伺服器接收使用者傳給伺服器的資料，然後再冒充使用者把資料傳給真正的伺服器。
而SSH是目前較可靠，專為遠端登入會話和其他網路服務提供安全性的協定。利用SSH協定可以有效防止遠端管理過程中的資訊泄露問題。透過SSH可以對所有傳輸的資料進行加密，也能夠防止DNS欺騙和IP欺騙。
SSH之另一項優點為其傳輸的資料是經過壓縮的，所以可以加快傳輸的速度。SSH有很多功能，它既可以代替Telnet，又可以為FTP、POP、甚至為PPP提供一個安全的「通道」。
安全套接層（Secure Sockets Layer，SSL）及其繼任者傳輸層安全（Transport Layer Security，TLS）是為網路通信提供安全及數據完整性的一種安全協議。TLS與SSL在傳輸層對網路連接進行加密。
介紹
由於Web上有時要傳輸重要或敏感的數據，因此Netscape公司在推出Web瀏覽器首版的同時，提出了安全通信協議SSL(Secure Socket Layer),目前已有2.0和3.0版本。SSL採用公開密鑰技術。其目的是保證兩個應用間通信的保密性和可靠性，可在伺服器和客戶機兩端同時實現支持。目前，利用公開密鑰技術的SSL協議，並已成為Internet上保密通訊的工業標準。現行Web瀏覽器普遍將HTTP和SSL相結合，從而實現安全通信。
安全通信協議(SSL)是在 Internet 基礎上提供的一種保證私密性的安全協議。在客戶端與伺服器間傳輸的數據是通過使用對稱演算法（如 DES 或 RC4）進行加密的。公用密鑰演算法（通常為 RSA）是用來獲得加密密鑰交換和數字簽署的，此演算法使用伺服器的SSL數字憑證中的公用密鑰。它能使客戶/伺服器應用之間的通信不被攻擊者竊聽，並且始終對伺服器進行認證，還可選擇對客戶進行認證。SSL協議要求建立在可靠的傳輸層協議 (例如：TCP) 之上。
SSL協議的優勢在於它是與應用層協議獨立無關的。高層的應用層協議 (例如：HTTP，FTP，TELNET … ) 能透明的建立於SSL協議之上。SSL協議在應用層協議通信之前就已經完成加密演算法、通信密鑰的協商以及伺服器認證工作。在此之後應用層協議所傳送的數據都會被加密，從而保證通信的私密性。
理清名稱上的的混淆，SSL(Secure Socket Layer)是netscape公司設計的主要用於web的安全傳輸協議。這種協議在WEB上獲得了廣泛的應用。IETF(www.ietf.org)將SSL作了標準化，即RFC2246,並將其稱為TLS（Transport Layer Security），從技術上講，TLS1.0與SSL3.0的差別非常微小。
TLS利用密鑰演算法在網際網路上提供端點身份認證與通訊保密，其基礎是公鑰基礎設施（PKI）。不過在實現的典型例子中，只有網路服務者被可靠身份驗證，而其客戶端則不一定。這是因為公鑰基礎設施普遍商業運營，電子簽名證書要花大錢購買，普通大眾很難買得起證書。協議的設計在某種程度上能夠使客戶端/伺服器應用程序通訊本身預防竊聽、干擾（Tampering）、和消息偽造。
TLS包含三個基本階段：
在第一階段，客戶端與伺服器協商所用密碼演算法。 當前廣泛實現的演算法選擇如下：
- 公鑰私鑰非對稱密鑰保密系統：RSA、Diffie-Hellman、DSA及Fortezza；
- 對稱密鑰保密系統：RC2、RC4、IDEA、DES、Triple DES及AES；
- 單向散列函數：MD5及SHA。
[編輯]工作方式
以下簡要介紹SSL協議的工作方式。客戶端要收發幾個握手信號：
- 發送一個ClientHello消息，說明它支持的密碼演算法列表、壓縮方法及最高協議版本，也發送稍後將被使用的隨機數。
- 然後收到一個ServerHello消息，包含伺服器選擇的連接參數，源自客戶端初期所提供的ClientHello。
- 當雙方知道了連接參數，客戶端與伺服器交換證書（依靠被選擇的公鑰系統）。這些證書通常基於X.509，不過已有草案支持以OpenPGP為基礎的證書。
- 伺服器請求客戶端公鑰。客戶端有證書即雙向身份認證，沒證書時隨機生成公鑰。
- 客戶端與伺服器通過公鑰保密協商共同的主私鑰（雙方隨機協商），這通過精心謹慎設計的偽隨機數功能實現。結果可能使用Diffie-Hellman交換，或簡化的公鑰加密，雙方各自用私鑰解密。所有其他關鍵數據的加密均使用這個「主密鑰」。
數據傳輸中記錄層（Record layer）用於封裝更高層的HTTP等協議。記錄層數據可以被隨意壓縮、加密，與消息驗證碼壓縮在一起。每個記錄層包都有一個Content-Type段用以記錄更上層用的協議。
TLS/SSL有多樣的安全保護措施：
- 所有的記錄層數據均被編號，用於消息驗證碼校驗。
PERT
PERT is a method to analyze the involved tasks in completing a given project, especially the time needed to complete each task, and identifying the minimum time needed to complete the total project.
SIMM
A SIMM, or single in-line memory module, is a type of memory module containing random access memory used in computers from the early 1980s to the late 1990s. It differs from a dual in-line memory module (DIMM), the most predominant form of memory module today, in that the contacts on a SIMM are redundant on both sides of the module. SIMMs were standardised under the JEDEC JESD-21C standard.
訂閱：
文章 (Atom)